Unique Elements in Sorted Array Editorial

Practice Problem Link: Unique Elements in Sorted Array | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array A, find the size of array A after removing the duplicate elements.

Naive Approach

We can just insert all the elements of the array in a set and return the size of the set.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int removeDuplicates(vector<int> &A) {
   unordered_set<int> duplicateRemoved;
   for (int i = 0; i < A.size(); i++) {
       duplicateRemoved.insert(A[i]);
   }
   return (int)duplicateRemoved.size();
}

Java

class Solution {
   int removeDuplicates(int[] A) {
       HashSet<Integer> duplicateRemoved = new HashSet<>();
       for (int i = 0; i < A.length; i++) {
           duplicateRemoved.add(A[i]);
       }
       return (int)duplicateRemoved.size();
   }
}

Optimal Approach

We will use the fact that the array is sorted to our advantage. Consider the count of unique elements initially to be the size of the array.

We keep two pointers at the endpoints of the array and check for duplicates at those indexes.

If duplicates are found, decrement the count of distinct elements accordingly. Finally, return the updated count.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int removeDuplicates(vector<int> &A) {
   int count = A.size(), left = 0, right = (int)A.size() - 1;
   while (left < right) {
       while (left != right && A[left] == A[left + 1]) {
           count--;
           left++;
       }
       while (left != right && A[right] == A[right - 1]) {
           count--;
           right--;
       }
       left++;
   }
   return count;
}

Java

class Solution {
   int removeDuplicates(int[] A) {
       int count = A.length, left = 0, right = A.length - 1;
       while (left < right) {
           while (left != right && A[left] == A[left + 1]) {
               count--;
               left++;
           }
           while (left != right && A[right] == A[right - 1]) {
               count--;
               right--;
           }
           left++;
       }
       return count;
   }
}