Remove Duplicates from Sorted Array
You are given a sorted integer array' ARR' of size 'N'. You need to remove the duplicates from the array such that each element appears only once. Return the length of this new array.

Note:

Do not allocate extra space for another array. You need to do this by modifying the given input array in-place with O(1) extra memory.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains an integer ‘N’ denoting the number of elements in the array. The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.

Output format:

For each test case, return the length of the modified array.

Note:

You don't need to print anything, it has already been taken care of. Just Implement the given function.

Constraints :

1

Question

Remove Duplicates from Sorted Array

You are given a sorted integer array' ARR' of size 'N'. You need to remove the duplicates from the array such that each element appears only once. Return the length of this new array.

Note:

Do not allocate extra space for another array. You need to do this by modifying the given input array in-place with O(1) extra memory.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array. 

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.

Output format:

For each test case, return the length of the modified array.

Note:

You don't need to print anything, it has already been taken care of. Just Implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 10^5
-10^9 <= ARR[i] <=10^9

Where ‘ARR[i]’ is the value of elements of the array.

Time limit: 1 sec

Accepted Answer

The task is to remove duplicates from a sorted integer array in-place and return the length of the modified array.

Use two pointers, one for iterating through the array and another for keeping track of the unique elements.
Compare the current element with the next element. If they are the same, move the second pointer forward.
If they are different, update the first pointer and replace the element at the first pointer with the unique element.
Continue this process until the end of the array and return the position of the first pointer as the length of the modified array.

Accepted Answer

First i presented the solution using extra Space (Always Start from a worst time complexity )

Step 1: I take an auxiliary array temp[] to store unique elements.
Step 2:I traversed input array and one by one copy unique elements of arr[] to temp[]. and also keep track of count of unique elements. Let this count be j.
Step 3: and lastly i copied j elements from temp[] to arr[] and return j.
the interviewer smiling said can u further optimise it and i said sure ...
Time Complexity : o(n)
Space Complexity : o(n)

Method 2:
Time Complexity : o(n)
Space Complexity : o(1)
(Constant extra space)
I just maintained a separate index for same array as maintained for different array in Method 1.

Accepted Answer

Two Pointer

We know that the array is sorted, and hence all the occurrences of a number will be clustered together. Keeping this in mind, we keep two pointers 'i' and ‘j’, where ‘i’ is the slow pointer and ‘j’ is the fast pointer.

Now, as long as ‘ARR[i]’ == ‘ARR[j]’ -> we keep on incrementing ‘j’ to skip all the duplicates.

Now, when we encounter ‘ARR[i]’ != ‘ARR[j]’ -> the duplicate run ends and hence now, we must copy the value of ‘ARR[j]’ to ‘ARR[i+1]’, ‘i’ is then incremented.

We repeat the same process until j reaches the end of the array. Return the value of ‘i’ at the end.

Space Complexity: O(1)Explanation:

O(1).

Since constant extra space is required, thus the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), Where N is the length of the array.

Since we will do N - 1 checks and thus the time complexity will be O(N).

Java (SE 1.8)

/*
	Time complexity: O(N) 
	Space complexity: O(1)
	
	Where 'N' is the length of the array.
*/

import java.util.ArrayList;

public class Solution {
    public static int removeDuplicates(ArrayList arr, int n) {
        // First pointer.
        int i = 0;

        // Second pointer traversing from 1 to n.
        for (int j = 1; j < n; j++) {
            // If not duplicates increment first pointer and check again
            if (arr.get(j) != arr.get(i)) {
                i++;
                arr.set(i, arr.get(j));
            }
        }
        // Return length == (index of first pointer when second reaches end) + 1.
        return i + 1;
    }
}

Python (3.5)

"""
	Time complexity: O(N) 
    Space complexity: O(1)
    
    Where 'N' is the length of the array.
"""

def removeDuplicates(arr, n):
    # First pointer.
    i = 0

    # Second pointer traversing from 1 to n.
    for j in range(1, n):
        # If not duplicates increment first pointer and check again.
        if (arr[j] != arr[j-1]):
            arr[i] = arr[j]
            i += 1
    
    # Return length == (index of first pointer when second reaches end) + 1.
    return i + 1

C++ (g++ 5.4)

/*
    Time complexity: O(N) 
    Space complexity: O(1)
    
    Where 'N' is the length of the array.
*/

int removeDuplicates(vector &arr, int n) {
    // First pointer.
    int i = 0;

    // Second pointer traversing from 1 to n.
    for (int j = 1; j < n; j++) {
        //  If not duplicates increment first pointer and check again.
        if (arr[j] != arr[j-1]) {
            arr[i++] = arr[j];
        }
    }
    // Return length == (index of first pointer when second reaches end) + 1.
    return i + 1;
}

You are given a sorted integer array' ARR' of size 'N'. You need to remove the duplicates from the array such that each element appears only once. Return the length of this new array.

Note:

Input format:

Output format:

Note:

Constraints :

Top Newgen Software Technologies Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Newgen Software Technologies Software Developer