Remove Duplicates from Sorted Array
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.
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,_,_,_,_]
=> 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.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int removeDuplicates(vector<int>& 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
#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]
#include <iostream>
#include <vector>
using namespace std;
int removeDuplicates(vector<int>& 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)