Problem Description

You are given an integer array nums that is sorted in non-decreasing order. Your task is to remove duplicates from this array in-place such that each unique element appears at most twice. The relative order of elements must be preserved.

The key requirements are:

• Modify the array in-place (cannot create a new array)
• Use only O(1) extra memory
• Each unique number can appear at most 2 times
• Return the length k of the modified array
• The first k elements of nums should contain the final result

For example:

• If nums = [1,1,1,2,2,3], after removing duplicates where each element appears at most twice, the array becomes [1,1,2,2,3,_] where _ represents any value (doesn't matter). The function should return k = 5.

The solution uses a two-pointer technique where:

• Variable k tracks the position where the next valid element should be placed
• For each element x in the array:
  • If k < 2 (first two elements are always valid) or x != nums[k-2] (current element is different from the element two positions back), we place x at position k and increment k
  • Otherwise, we skip the element as it would create more than 2 duplicates

The algorithm efficiently processes the array in a single pass with O(n) time complexity and O(1) space complexity.

Intuition

Since the array is sorted, all duplicate elements are adjacent to each other. This is the key insight that makes the problem solvable in a single pass.

Think about what we're trying to achieve: we want to keep at most 2 copies of each element. As we traverse the array, we need to decide whether to keep or skip each element.

The critical observation is: if we've already kept some elements in our result (let's say the first k elements are our valid result so far), then for a new element x, we should only add it if:

1. We have fewer than 2 elements in our result (the first two elements can always be added), OR
2. The element x is different from the element that's 2 positions back in our result

Why check 2 positions back? Because if x equals nums[k-2], it means we already have at least 2 copies of x in our result (at positions k-2 and k-1). Adding another would violate our constraint.

Let's trace through an example: nums = [1,1,1,2,2,3]

• Start with k = 0
• Element 1 (first): k < 2, so add it. k = 1
• Element 1 (second): k < 2, so add it. k = 2
• Element 1 (third): k = 2, check if 1 != nums[0] (which is 1). They're equal, so skip.
• Element 2 (first): k = 2, check if 2 != nums[0] (which is 1). They're different, so add it. k = 3
• Element 2 (second): k = 3, check if 2 != nums[1] (which is 1). They're different, so add it. k = 4
• Element 3: k = 4, check if 3 != nums[2] (which is 2). They're different, so add it. k = 5

This approach naturally maintains the relative order and ensures no element appears more than twice, all while using just a single pointer k to track our position.

Learn more about Two Pointers patterns.

Solution Approach

The implementation uses a two-pointer technique with a single pass through the array:

Algorithm Steps:

1. Initialize a pointer k: Set k = 0 to track the position where the next valid element should be placed. This represents the length of our processed array.

2. Iterate through each element: For each element x in nums:

   • Check if element should be kept:
     • If k < 2: The first two elements are always valid (we can have up to 2 duplicates)
     • OR if x != nums[k-2]: The current element is different from the element two positions back in our valid array
   • If the condition is met:
     • Place the element: nums[k] = x
     • Increment the pointer: k += 1
   • Otherwise: Skip the element (it would create more than 2 duplicates)

3. Return the result: After traversing the entire array, return k as the length of the modified array.

Key Pattern - Why nums[k-2]?

The check x != nums[k-2] is the core of this algorithm:

• nums[k-2] represents the element that's 2 positions back in our valid result
• If x equals nums[k-2], then we know:
  • nums[k-2] = x (by definition)
  • nums[k-1] = x (because the array is sorted, and we wouldn't have added nums[k-1] if it wasn't equal to or greater than nums[k-2])
• Therefore, adding x would create a third duplicate, which violates our constraint

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array. We traverse the array exactly once.
• Space Complexity: O(1) as we only use a constant amount of extra space (the variable k).

Extension to k duplicates:

This approach can be generalized to allow at most k duplicates by:

• Keeping the first k elements automatically
• For subsequent elements, checking against nums[pos-k] instead of nums[pos-2]

This makes the solution flexible and applicable to similar problems with different duplicate limits.

Example Walkthrough

Let's trace through a small example to illustrate the solution approach.

Input: nums = [0,0,1,1,1,2,3,3]

We'll use a pointer k to track where the next valid element should be placed.

Initial State:

• k = 0
• Array: [0,0,1,1,1,2,3,3]

Step 1: Process x = 0 (index 0)

• Check: k < 2? Yes (k=0)
• Action: Place 0 at position k=0, increment k
• nums[0] = 0, k = 1
• Array: [0,0,1,1,1,2,3,3]

Step 2: Process x = 0 (index 1)

• Check: k < 2? Yes (k=1)
• Action: Place 0 at position k=1, increment k
• nums[1] = 0, k = 2
• Array: [0,0,1,1,1,2,3,3]

Step 3: Process x = 1 (index 2)

• Check: k < 2? No (k=2). Check: 1 != nums[0]? Yes (1 ≠ 0)
• Action: Place 1 at position k=2, increment k
• nums[2] = 1, k = 3
• Array: [0,0,1,1,1,2,3,3]

Step 4: Process x = 1 (index 3)

• Check: k < 2? No (k=3). Check: 1 != nums[1]? Yes (1 ≠ 0)
• Action: Place 1 at position k=3, increment k
• nums[3] = 1, k = 4
• Array: [0,0,1,1,1,2,3,3]

Step 5: Process x = 1 (index 4)

• Check: k < 2? No (k=4). Check: 1 != nums[2]? No (1 = 1)
• Action: Skip this element (would create 3rd duplicate)
• Array: [0,0,1,1,1,2,3,3] (unchanged)

Step 6: Process x = 2 (index 5)

• Check: k < 2? No (k=4). Check: 2 != nums[2]? Yes (2 ≠ 1)
• Action: Place 2 at position k=4, increment k
• nums[4] = 2, k = 5
• Array: [0,0,1,1,2,2,3,3]

Step 7: Process x = 3 (index 6)

• Check: k < 2? No (k=5). Check: 3 != nums[3]? Yes (3 ≠ 1)
• Action: Place 3 at position k=5, increment k
• nums[5] = 3, k = 6
• Array: [0,0,1,1,2,3,3,3]

Step 8: Process x = 3 (index 7)

• Check: k < 2? No (k=6). Check: 3 != nums[4]? Yes (3 ≠ 2)
• Action: Place 3 at position k=6, increment k
• nums[6] = 3, k = 7
• Array: [0,0,1,1,2,3,3,3]

Final Result:

• Return k = 7
• First 7 elements: [0,0,1,1,2,3,3]
• Each unique element appears at most twice ✓

The key insight: by checking nums[k-2], we ensure that if an element already appears twice in our result (at positions k-2 and k-1), we don't add a third copy.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once with a single for loop. Each operation inside the loop (comparison, assignment, and increment) takes constant time O(1). Therefore, the overall time complexity is linear.

Space Complexity: O(1). The algorithm modifies the input array in-place and only uses a constant amount of extra space for the variable k and the loop variable x. No additional data structures are created that scale with the input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing the Two Pointers' Roles

Pitfall: Many developers mistakenly think k represents an index in the original array or try to use it to compare with indices of unprocessed elements. This leads to incorrect comparisons like checking nums[i-2] instead of nums[k-2].

Why it happens: The variable naming and the fact that we're iterating through the same array we're modifying can create confusion about which part of the array represents the "processed" valid elements versus the "unprocessed" original elements.

Solution:

• Think of nums[0:k] as your "result array" being built
• k is the size of this result array AND the position where the next valid element goes
• Always compare with positions in the result portion (nums[k-2]), not the iteration position

2. Off-by-One Errors with the k-2 Check

Pitfall: Accessing nums[k-2] when k < 2 causes an index out of bounds error or incorrect array access with negative indices (in Python, negative indices wrap around).

Example of incorrect code:

def removeDuplicates(self, nums: List[int]) -> int:
    k = 0
    for x in nums:
        # WRONG: This will access nums[-2] and nums[-1] when k is 0 or 1
        if x != nums[k-2]:  
            nums[k] = x
            k += 1
    return k

Solution: Always guard the nums[k-2] check with k < 2 condition first:

if k < 2 or x != nums[k-2]:  # Correct: short-circuit evaluation prevents invalid access

3. Attempting to Delete Elements Instead of Overwriting

Pitfall: Trying to actually remove elements from the array using operations like del, pop(), or list slicing, which violates the O(1) space requirement and in-place modification constraint.

Incorrect approach:

def removeDuplicates(self, nums: List[int]) -> int:
    i = 2
    while i < len(nums):
        if nums[i] == nums[i-2]:
            nums.pop(i)  # WRONG: O(n) operation inside loop, modifies array size
        else:
            i += 1
    return len(nums)

Solution: Stick to the overwriting approach - don't actually remove elements, just overwrite positions and return the new logical length.

4. Misunderstanding the Return Value

Pitfall: Returning the wrong value or misunderstanding what k represents. Some might return k-1 thinking it's the last valid index, or return the number of elements removed instead of kept.

Solution: Remember that k represents:

• The COUNT of valid elements (not the last index)
• The LENGTH of the modified portion of the array
• The next position where a valid element would be placed (which equals the count)

5. Forgetting the Array is Already Sorted

Pitfall: Adding unnecessary complexity by trying to handle unsorted arrays or checking multiple previous elements unnecessarily.

Why it matters: Because the array is sorted, if nums[k-2] == x, we know that nums[k-1] == x as well (since we only add elements that maintain the sorted order). This is why checking just nums[k-2] is sufficient.

Solution: Trust the sorted property - you only need to check against the element 2 positions back, not both nums[k-1] and nums[k-2].