Remove Duplicates from Sorted Array II
This is a follow-up to the classic Remove Duplicates from Sorted Array problem. The twist? Now you're allowed to keep each element at most twice in the sorted array.
After placing the final result in the first k slots of array, return k.
=> 1 <= arr.length <= 3 * 104 => -104 <= arr[i] <= 104 => Don't use extra memory. Space Complexity should be O(1) => arr is sorted in ascending order.
1. Brute Force Approach
We can use a Map (or Dictionary) to count the occurrences of each element. Then, we rebuild a new array by adding each number at most twice.
This approach is simple and easy to explaining in interviews before optimizing.
- Use a Map to track counts.
- Create a new array.
- Copy each element at most twice.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int removeDuplicates(vector<int>& arr) {
unordered_map<int, int> freq;
vector<int> result;
for (int num : arr) {
freq[num]++;
if (freq[num] <= 2) {
result.push_back(num);
}
}
for (int i = 0; i < result.size(); ++i) {
arr[i] = result[i];
}
return result.size();
}
int main() {
vector<int> arr = {1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 5};
int k = removeDuplicates(arr);
cout << "k = " << k << endl;
for (int i = 0; i < k; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}k = 7 1 1 2 2 3 3 5
Time Complexity : O(n)
Space Complexity : O(n)
2. Better Approach (Count and Shift)
Since the array is sorted, duplicates will always be grouped together. We can count consecutive occurrences of each number and only keep it at most twice by shifting elements forward as we go.
This approach improves upon the brute-force method by avoiding a map and working mostly in-place, using just a few variables for counting.
- Count consecutive occurrences.
- If count <= 2, retain element.
- Shift elements forward accordingly.
#include <iostream>
#include <vector>
using namespace std;
int removeDuplicates(vector<int>& arr) {
int n = arr.size();
if (n <= 2) return n;
int k = 1;
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1]) {
count++;
} else {
count = 1;
}
if (count <= 2) {
arr[k++] = arr[i];
}
}
return k;
}
int main() {
vector<int> arr = {1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 5};
int k = removeDuplicates(arr);
cout << "k = " << k << endl;
for (int i = 0; i < k; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}k = 7 1 1 2 2 3 3 5
Time Complexity : O(n)
Space Complexity : O(1)
3. Optimal Approach (Two-Pointer Strategy)
The optimal way to solve this problem is by using two pointers
- A read pointer j to traverse the array.
- Use a write pointer i to mark where to insert next valid element.
- For each arr[j], compare it with arr[i - 2]. If it's not the same, allow it.
#include <iostream>
#include <vector>
using namespace std;
int removeDuplicates(vector<int>& arr) {
int n = arr.size();
if (n <= 2) return n;
int i = 2;
for (int j = 2; j < n; j++) {
if (arr[j] != arr[i - 2]) {
arr[i++] = arr[j];
}
}
return i;
}
int main() {
vector<int> arr = {1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 5};
int k = removeDuplicates(arr);
cout << "k = " << k << endl;
for (int i = 0; i < k; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}k = 7 1 1 2 2 3 3 5
Time Complexity : O(n)
Space Complexity : O(1)