77. Remove Duplicates from Sorted Array II

Keep a write index k. Accept the current value if we've written fewer than two elements, or if it differs from the value two slots back (nums[k-2]) — that guarantees at most two copies of any value.

Idea

We want at most two of each value, and the array is sorted so equal values are adjacent. Maintain a write index k. A value is allowed if either we've written fewer than 2 so far, or it's different from what sits two positions back (nums[k-2]). Since the array is sorted, nums[k-2] == x means we've already kept two copies of x.

(This platform returns the resulting kept array — its length is the required k.)

Algorithm

1. k = 0.
2. For each x in nums: if k < 2 or x != nums[k-2], write nums[k] = x and k += 1.
3. Return nums[:k].

Worked example: [1,1,1,2,2,3]

• 1 (k<2) → keep, k=1. 1 (k<2) → keep, k=2. 1 (== nums[0]) → skip. 2 (≠ nums[0]=1) → keep, k=3. 2 (≠ nums[1]=1) → keep, k=4. 3 (≠ nums[2]=2) → keep, k=5.

Kept = [1,1,2,2,3].

Complexity

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

import java.util.Arrays;

class Solution {
    public int[] removeDuplicates(int[] nums) {
        int k = 0;
        for (int x : nums) {
            if (k < 2 || x != nums[k - 2]) {
                nums[k] = x;
                k++;
            }
        }
        return Arrays.copyOf(nums, k);
    }
}