Remove Duplicates from Sorted Array II
190 Views
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.
Given a sorted integer array in ascending order , remove all duplicates from this array so that each unique element appears at most twise in this array. also maintain relative order of the elements in array.
After placing the final result in the first k slots of array, return k.
Example 1
Input :-arr => [11,11,11,52,52,83,92,101,101]
Output :- k => 8 , arr => [11,11,52,52,83,92,101,101,_]
Constraints :-
=> 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
- Use a Map to track counts.
- Create a new array.
- Copy each element at most twice.
C++
Java
C#
Python
#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)
- Count consecutive occurrences.
- If count <= 2, retain element.
- Shift elements forward accordingly.
C++
Java
C#
Python
#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)
- 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.
C++
Java
C#
Python
Java Script
#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)