Remove Duplicates From Sorted Array II - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

The problem asks to remove duplicates from a sorted array in-place, allowing each unique element to appear at most twice, and return the length of the resulting array. Since the array is sorted, duplicates are adjacent, and we need to ensure each element appears no more than twice in the final array.

The solution uses a two-pointer approach with a counter to track the frequency of each element, ensuring at most two occurrences are kept. Here’s how it operates:

Initial Setup: We initialize j to 1, indicating where the next valid element (within the allowed frequency) should be placed, since the first element is always included. A variable count is set to 1 to track the frequency of the current element, starting with the first element.
Iterating and Counting: We loop through the array from index 1 to the end. For each element at index i:
- If nums[i] == nums[i-1], the element is a duplicate, so we increment count.
- If nums[i] != nums[i-1], we’ve encountered a new element, so we reset count to 1.
Placing Valid Elements: If count <= 2, the current element is within the allowed frequency, so we place it at nums[j] and increment j. This ensures that each element appears at most twice in the output subarray.
Result: After the loop, j represents the length of the array with each element appearing at most twice, and the first j elements of nums contain the valid elements in sorted order. We return j.
Why This Works: The sorted array ensures duplicates are adjacent, allowing us to track element frequencies by comparing with the previous element. The count variable ensures we include at most two occurrences of each element, and the j pointer builds the result in-place, maintaining the relative order of elements.
Time and Space Complexity: The solution iterates through the array once, resulting in a time complexity of O(n). Since it modifies the array in-place, the space complexity is O(1).

Code Solution

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        count = 1
        n = len(nums)

        for i in range(1, n):
            if nums[i] == nums[i-1]:
                count += 1
            else:
                count = 1
            
            if count <= 2:
                nums[j] = nums[i]
                j += 1
        
        return j
         # Time: O(n)
         # Space: O(1)

#include <vector>

class Solution {
public:
    int removeDuplicates(std::vector<int>& nums) {
        int j = 1;
        int count = 1;
        int n = nums.size();

        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                count = 1;
            }

            if (count <= 2) {
                nums[j] = nums[i];
                j++;
            }
        }

        return j;
    }
};

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        int count = 1;
        int n = nums.length;

        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                count = 1;
            }

            if (count <= 2) {
                nums[j] = nums[i];
                j++;
            }
        }

        return j;
    }
}

var removeDuplicates = function(nums) {
    var j = 1;
    var count = 1;
    var n = nums.length;

    for (var i = 1; i < n; i++) {
        if (nums[i] === nums[i - 1]) {
            count++;
        } else {
            count = 1;
        }

        if (count <= 2) {
            nums[j] = nums[i];
            j++;
        }
    }

    return j;
};

Detailed Explanation

Understanding the Problem

The task is to modify a sorted array in-place such that each element appears at most twice, and return the new length of the array. Since the array is already sorted in non-decreasing order, any duplicates will be adjacent. The key challenge is to ensure that no value appears more than twice while preserving the relative order of valid elements, all without using extra space.

Core Strategy: Two Pointers with Frequency Tracking

To solve this problem efficiently, we employ a two-pointer approach combined with a counter to track the number of times a particular value appears consecutively. We use a write pointer j to track the position where the next valid element should be placed. The read pointer i scans through the array, while a counter count keeps track of how many times the current element has appeared so far.

Implementation Details

We start by initializing j = 1 since the first element is always valid, and count = 1 for the first occurrence. Then, we iterate over the array from index 1 to the end:

If nums[i] == nums[i - 1], we increment count since it's a duplicate of the previous number.
If nums[i] != nums[i - 1], we reset count to 1 because we've encountered a new unique value.
If count <= 2, the current number is allowed to stay in the array (no more than twice). So, we place it at nums[j] and increment j.

This logic ensures that each unique number appears at most twice in the result. The elements are placed in the first j positions of the array, forming the correct output in-place.

Example Walkthrough

For input [1,1,1,2,2,3], the algorithm processes the first two 1s normally. When it sees the third 1, it skips it because count becomes 3. It then processes the 2s similarly, keeping the first two and skipping any beyond that. The final array becomes [1,1,2,2,3], and the returned length is 5.

Time and Space Complexity

The solution has a linear time complexity of O(n), where n is the length of the input array. Each element is visited exactly once. It also satisfies the space requirement of O(1) since it modifies the input array in-place without using any additional data structures.

Why This Approach Is Effective

This method leverages the fact that the array is sorted to efficiently manage duplicates by comparing each element with the one before it. The use of a counter ensures that we only accept up to two occurrences of any value. By using two pointers and tracking frequency, we maintain an optimized, readable, and space-efficient solution that aligns well with real-world in-place data cleaning tasks.

Get Personalized Support at AlgoMap Bootcamp 💡