Remove Duplicates from Sorted Array II

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.

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).

Approach: Two Pointers

Explanation

We can solve this problem efficiently using two pointers:

Initialize two pointers: k at index 2 (since the first two elements can always be kept) and i to iterate through the array starting from index 2.
Iterate through the array with i.
If the current element is different from the element two positions before in the result array, it's a new element or the second occurrence of an element. Copy it to the position k and increment k.
After the iteration, k will be the number of elements in the result.

Time Complexity: O(n)

Space Complexity: O(1)

Implementation

Java Solution

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) return nums.length;

        int k = 2; // pointer for the position to place the next element

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] != nums[k-2]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
}

C++ Solution

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) return nums.size();

        int k = 2; // pointer for the position to place the next element

        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] != nums[k-2]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
};

Explanation with Example

Let's walk through the solution using Example 1:

nums = [1,1,1,2,2,3]

Initialize k = 2 (first two elements are always kept) and start iterating with i = 2.
nums[2] = 1 == nums[0], so we skip it: k remains 2
nums[3] = 2 != nums[0], so we keep it: nums[2] = 2, k = 3
nums[4] = 2 != nums[1], so we keep it: nums[3] = 2, k = 4
nums[5] = 3 != nums[2], so we keep it: nums[4] = 3, k = 5

After the iteration, k = 5, and the first 5 elements of nums are [1,1,2,2,3].

This approach is efficient because:

It only requires a single pass through the array (O(n) time complexity).
It doesn't use any extra space (O(1) space complexity).
It modifies the array in-place, satisfying the problem requirement.
It maintains the relative order of the elements, as required by the problem.
It ensures that each element appears at most twice in the result.

The key insight in this algorithm is comparing the current element with the element two positions before in the result array. This allows us to keep at most two occurrences of each element while maintaining the order.

Remove Duplicates from Sorted Array

Majority Element