LogIn
I don't have account.

Remove Duplicates from Sorted Array

Code Crafter

146 Views

When it comes to mastering array manipulation in coding interviews, the problem of removing duplicates from a sorted array is a must-know. It not only tests your understanding of in-place algorithms but also your ability to optimize space and time complexity.

Given an integer sorted array in ascending order , remove all duplicates from this array so that each unique element appears only once in this array. also maintain relative order of the elements in array.

Assume that there are k unique elements in the array. Modify the array arr so that its first k elements are unique and in the same relative order.

Example 1

Input :- [2,3,4,4,4,5,6,7,8,8,8,9]

Output :-k => 8 , arr => [2,3,4,5,6,7,8,9,_,_,_,_]

Example 2
Input :-[1,2,3]
Output :- k => 3 , arr => [1,2,3]
Constraints :-
=> 1 <= arr.length <= 3 * 104
=> -100 <= arr[i] <= 100
=> arr is sorted in ascending order.

Brute Force

  • Use a Set to store unique elements.
  • Copy back to the original array.
C++
Java
C#
Python
Copy
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int removeDuplicates(vector<int>&amp; arr) {
    set<int> uniqueSet(arr.begin(), arr.end());
    int index = 0;
    for (int num : uniqueSet) {
        arr[index++] = num;
    }
    return uniqueSet.size();
}

int main() {
    vector<int> arr = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    int k = removeDuplicates(arr);
    cout << "Unique elements count = " << k << ", arr = ";
    for (int i = 0; i < k; ++i)
        cout << arr[i] << " ";
    return 0;
}
Unique elements count = 5, arr = 0 1 2 3 4

⏱️ Time Complexity : O(n)

🧪 Space Complexity : O(n)

In-place with Shifting

  • If a duplicate is found, shift all remaining elements to the left
C++
Java
C#
Python
Copy
#include <iostream>
using namespace std;

int removeDuplicates(int arr[], int n) {
    int i = 0;
    while (i < n - 1) {
        if (arr[i] == arr[i + 1]) {
            for (int j = i + 1; j < n - 1; j++) {
                arr[j] = arr[j + 1];
            }
            n--;
        } else {
            i++;
        }
    }
    return n;
}
int main() {
    int arr[] = {0, 0, 1, 1, 2, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = removeDuplicates(arr, n);
    cout << "Unique elements count = " << k << ", arr = ";
    for (int i = 0; i < k; i++) cout << arr[i] << " ";
    return 0;
}
Unique elements count = 4, arr = 0 1 2 3

⏱️ Time Complexity : O(n^2)

🧪 Space Complexity : O(1)

Optimal Two-Pointer Technique

  • Use two pointers, i for last unique index and j for scanning new elements
  • If arr[j] != arr[i], move i forward and copy arr[j]
C++
Java
C#
Python
Java Script
Copy
#include <iostream>
#include <vector>

using namespace std;

int removeDuplicates(vector<int>&amp; arr) {
    if (arr.empty()) return 0;
    int i = 0;
    for (int j = 1; j < arr.size(); j++) {
        if (arr[j] != arr[i]) {
            i++;
            arr[i] = arr[j];
        }
    }
    return i + 1;
}

int main() {
    vector<int> arr = {0, 0, 1, 1, 2, 2, 3, 3, 4};
    int k = removeDuplicates(arr);
    cout << "Unique elements count = " << k << ", arr = ";
    for (int i = 0; i < k; i++) cout << arr[i] << " ";
    return 0;
}
Unique elements count = 5, arr = 0 1 2 3 4

⏱️ Time Complexity : O(n)

🧪 Space Complexity : O(1)

Summary

Approach Time Space In-Place Notes
Brute Force (Set) O(n) O(n) Uses extra space
In-place with Shifting O(n²) O(1) Too many unnecessary shifts
Optimal (Two Pointer) O(n) O(1) Best and most efficient solution