80. Remove Duplicates From Sorted Array II - Explanation

1. Brute Force

Intuition

We allow each element to appear at most twice. When we find more than two consecutive duplicates, we shift all subsequent elements left to overwrite the extras. This in-place modification is straightforward but inefficient due to repeated shifting operations.

Algorithm

Handle arrays with 2 or fewer elements as base cases.
Iterate through the array looking for duplicate pairs.
When a duplicate pair is found, count how many extras exist beyond the allowed two.
Shift all elements after the extras to the left to fill the gap.
Reduce the effective array length and continue scanning.
Return the final length.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n
        i = 0
        while i < n - 1:
            if nums[i] == nums[i + 1]:
                j = i + 2
                cnt = 0
                while j < n and nums[i] == nums[j]:
                    j += 1
                    cnt += 1
                for k in range(i + 2, n):
                    if j >= n:
                        break
                    nums[k] = nums[j]
                    j += 1
                n -= cnt
                i += 2
            else:
                i += 1
        return n

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Hash Map

Intuition

We count occurrences of each element using a hash map while preserving order. Then we reconstruct the array, writing each element at most twice. This uses extra space but separates the counting logic from the placement logic.

Algorithm

Count occurrences of each element while tracking their first appearance order.
Iterate through unique elements in order.
For each element, write it to the result position once, then write it again if it appeared more than once.
Return the final write position as the new length.

This approach ensures the array remains sorted since we process unique elements in order.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n

        count = Counter(nums)
        i = 0
        for num in count:
            nums[i] = num
            count[num] -= 1
            i += 1
            if count[num] >= 1:
                nums[i] = num
                count[num] -= 1
                i += 1
        return i

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Two Pointers

Intuition

We process groups of consecutive duplicates together. For each group, we write at most two copies to the result portion of the array. The left pointer tracks where to write, and the right pointer scans through the array finding groups.

Algorithm

Initialize left and right pointers at 0.
For each group of duplicates, count how many there are by advancing r.
Write min(2, count) copies of the element starting at position l.
Advance l accordingly and move to the next group.
Return l as the new length.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l, r = 0, 0

        while r < len(nums):
            count = 1
            while r + 1 < len(nums) and nums[r] == nums[r + 1]:
                r += 1
                count += 1

            for i in range(min(2, count)):
                nums[l] = nums[r]
                l += 1
            r += 1

        return l

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

4. Two Pointers (Optimal)

Intuition

The cleanest approach uses a single condition: we only write an element if the write position is less than 2 (first two elements always go through) OR the current element differs from the element two positions back in the result. This automatically limits each value to at most two occurrences.

Algorithm

Initialize the write pointer l at 0.
Iterate through each element in the array.
If l < 2 or the current element differs from nums[l - 2], write it at position l and increment l.
Return l as the new length.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = 0
        for num in nums:
            if l < 2 or num != nums[l - 2]:
                nums[l] = num
                l += 1
        return l

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Comparing with the Wrong Element

In the optimal two-pointer solution, you should compare nums[i] with nums[l - 2], not with nums[l - 1]. Comparing with l - 1 only checks if the current element differs from the previous one, which doesn't prevent more than two consecutive duplicates. You need to look back two positions to ensure at most two occurrences of any value.

Forgetting the Base Case

Arrays with 2 or fewer elements are already valid (each element can appear at most twice). Some solutions fail to handle these edge cases, leading to index out of bounds errors when checking nums[l - 2] with l < 2. Always either return early for small arrays or use a condition like l < 2 to bypass the comparison.

Modifying the Wrong Position

When using two pointers, the write pointer l should advance only after writing a valid element. A common bug is incrementing l before writing or writing to the wrong index. The pattern should be: check condition, write to nums[l], then increment l. Writing to nums[l++] in languages that support it keeps this atomic.