Problem Statement

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Links

Remove duplicates from sorted array 2

Constraints

1 <= nums.length <= 3 * 10^4
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

Examples

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]

Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Different Approaches

1️⃣ Two Pointers

Intuition:

Since the array is sorted, duplicates appear next to each other.

We need to keep at most two occurrences of each element.

Use a Two Pointer Pointers approach:

• Pointer i will track the position to insert the next valid element.
• Pointer j will iterate through the array.

We allow the first two elements always, From index 2 onwards, if nums[j] != nums[i-2], it's valid to keep it.

Dry Run:

Initialization:

i = 2

Start Iterating from j = 2 to n - 1

i = 2
j = 2 (loop)
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  1  |  1  |  2  |  2  |  3  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                      ^
                      |
                      i
                      j

    Compare nums[j] with nums[i-2]
    If nums[j] == nums[i-2]
       nums[2] == nums[0]
       1 == 1
       ❌ Skip (this is the 3rd occurrence of 1)

i = 2
j = 3 (loop)
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  1  |  1  |  2  |  2  |  3  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                      ^     ^
                      |     |
                      i     j

    Compare nums[j] with nums[i-2]
    If nums[j] == nums[i-2]
       nums[3] == nums[0]
            2 == 1
            False
       Set nums[i] = nums[j]
           nums[2] = 2
           i++ -> i = 3

i = 3
j = 4 (loop)
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  1  |  2  |  2  |  2  |  3  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                            ^     ^
                            |     |
                            i     j

    Compare nums[j] with nums[i-2]
    If nums[j] == nums[i-2]
       nums[4] == nums[1]
            2 == 1
            False
       Set nums[i] = nums[j]
           nums[3] = 2
           i++ -> i = 4

i = 4
j = 5 (loop)
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  1  |  2  |  2  |  2  |  3  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                  ^     ^
                                  |     |
                                  i     j

    Compare nums[j] with nums[i-2]
    If nums[j] == nums[i-2]
       nums[4] == nums[2]
            3 == 2
            False
       Set nums[i] = nums[j]
           nums[4] = 3
           i++ -> i = 5

Out of bounds:

Final State:

i = 5
j = 6 (loop) (out of bounds)
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  1  |  2  |  2  |  3  |  3  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                                        ^     ^
                                        |     |
                                        i     j
i points to the position just after the last valid element. Since arrays are zero-indexed, this means the first i elements are valid.

Code:

int removeDuplicates(vector<int>& nums) {
    int n = nums.size(); // Get the size of the input array

    // If the array has 2 or fewer elements, it already meets the condition
    if (n <= 2) return n;

    int i = 2;  // Start placing elements from the 3rd position (index 2)

    // Loop through the array starting from the 3rd element
    for (int j = 2; j < n; ++j) {
        // Compare current element with the element at position i-2
        // This checks if the current element is allowed (i.e., not more than twice)
        if (nums[j] != nums[i - 2]) {
            // If not equal, it's safe to include the current number
            nums[i] = nums[j]; // Place the number at the current write index
            ++i; // Move the write index forward
        }
        // If it *is* equal, it means we've already included two of these, so skip it
    }

    // After the loop, i represents the new length of the modified array
    return i;
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(1)