LogIn
I don't have account.

Remove Duplicates from Sorted Array II

Code Crafter

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
Copy
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int removeDuplicates(vector<int>&amp; 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
Copy
#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>&amp; 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
Copy
#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>&amp; 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)

Summary

Approach Time Space In-Place Notes
Brute Force O(n) O(n) Easy to understand, but violates space constraint
Better O(n) O(1) Manually manage duplicates
Optimal (2-Pointer) O(n) O(1) Clean, efficient and best choice