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
}

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(1)

Suggested Problems to Solve

• Find the most frequent character in a sentence.
• Remove elements to make array sorted.
• Remove duplicates from an unsorted array.
• Return the duplicate elements from a list and also the size of the list after removing those duplicates.
• Remove all elements that have duplicates in the array. All elements in the resultant array must be unique in the original array.

Happy Coding! Enjoy Algorithms!!