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)