Remove Duplicates in a Sorted Array-Interview Problem

Difficulty: Medium

Asked in: Google, Microsoft, Amazon

Understanding the Problem:

Given a sorted array that has some unique as well as some duplicate elements, your task is to remove all the duplicate elements from the given array and return the size of the new array that is not having any duplicate elements in it.

For example:

Input:  A={2,3,3,4,5,7,7,9}
Output: 6

Explanation: All the duplicate elements have been removed and new array is A={2,3,4,5,7,9} i.e. length 6.
Similarly,
Input: A={4,7,9,9,10,11,11}
Output: 5

Possible follow-up questions to ask the interviewer: →

Can we use extra space?( Ans: You can, however try to optimise the solution.)

You can try solving the question from here.

Solutions

We are going to discuss two possible ways to solve this problem:

Brute Force Solution
Solution with Index Pointer

Brute Force Solution

Solution idea

The idea here is create another array of size equal to the original array and to compare an element with other elements just adjacent to it. If there is a match, then there is a duplicate element present in the array. We will only copy the unique elements into auxiliary array and will also maintain a count of all the unique elements. After traversing the whole array we will copy all the elements of the auxiliary array back to the original array and return the original array.

Solution steps

We will create an auxiliary array of original array's size.
We will compare each element with the elements adjacent to it.
If the elements do not match, we will copy the unique elements into the auxiliary array while maintaining a count.
At last we will copy the contents of auxiliary array back to the original array. Returning the new size of the array will be good enough.

Pseudo-code

int removeDuplicatesFromSortedArray(int A[], int size)
{
   int index=0 
   int tempArr[size] 
   if(size <= 1) //Accessing i+1 will give garbage in this case
      return size
   for( i = 0 to size-2 )
   {
      if(A[i]!=A[i+1])
      {
        tempArr[index] = A[i]
        index += 1
      }
    }
   tempArr[index] = A[size-1]  //Store the last element
   index++;
   for( i = 0 to index-1 )
      A[i] = tempArr[i]
   return index
}

Complexity Analysis

Time Complexity: O(N), where N is the size of the array.

Space Complexity: O(N) (Why?)

Critical ideas to think!

Can we do it another way by using some extra space?( Hint : Think about Hashing related concepts and how feasible the solution is!)

Solution with Index Pointer

Solution idea

The idea in this solution is the same as the approach we followed in the above solution, but instead, we will store the unique elements in the same array. How can we do that?( Think! )

We can use the index variable used above to update the original array. The duplicates elements will be replaced by unique neighboring elements.

Solution steps

We will use a separate index for pointing the unique elements
We will shift the elements in the array by comparing two adjacent elements, if they are not equal we will take one as unique and put it at the index pointer’s location and we will again check the other element with its adjacent one.
This shifting will help in only having unique elements in the array.

Pseudo-code

int removeDuplicatesFromSortedArray(int A[], int size)
{
   if(size<=1)
     return size
   int index = 0
   for( i = 0 to size-2 )
   { 
     if(A[i] != A[i+1])
     {
       A[index] = A[i]
       index += 1
     }
   }
   A[index] = A[size-1]
   index++;
   return index
}