Master LeetCode 80: Remove Duplicates from Sorted Array II with a Simple Two‑Pointer Solution

Problem Overview

Given a sorted integer array nums, remove duplicates in‑place so that each distinct value appears at most twice and return the new length. Positions beyond the returned length are irrelevant (denoted by _).

Two‑Pointer Insight

The solution uses a fast pointer that scans every element and a slow pointer that marks the position to write the next kept element. The difficulty lies in deciding when the slow pointer should advance.

Core Rule

Only when nums[slow-2] != nums[fast] does the slow pointer accept the element and move forward; otherwise only fast advances.

This rule works because we allow at most two occurrences of each value. If the element two positions behind the slow pointer equals the current fast element, it would create a third duplicate, which must be rejected.

Step‑by‑Step Walkthrough (example nums = [1,1,1,2,2,3] )

Initial state: slow = fast = 2 (the first two elements are always valid).

Step 1 : nums[slow-2]=1, nums[fast]=1 → equal → reject, only fast moves to 3.

Step 2 : compare nums[slow-2]=1 with nums[fast]=2 → different → copy nums[fast] to nums[slow], increment both pointers (now slow=3, fast=4).

Step 3 : nums[slow-2]=1, nums[fast]=2 → different → copy, pointers become slow=4, fast=5.

Step 4 : nums[slow-2]=2, nums[fast]=3 → different → copy, pointers become slow=5, fast=6 (out of bounds, loop ends).

Final slow value is 5, and the valid prefix of the array is [1,1,2,2,3].

Final Implementation (Python, 10 lines)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n
        slow, fast = 2, 2
        while fast < n:
            if nums[slow - 2] != nums[fast]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

Key Takeaways

Initialize both pointers at index 2 because the first two elements are always allowed.

The slow pointer moves only when the element two steps behind differs from the current element, guaranteeing no more than two duplicates.

Generalization to “at most K” occurrences

Replace the constant 2 with k in both the initialization and the condition nums[slow-k] != nums[fast]. The algorithm remains identical.

class Solution:
    def removeDuplicates(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n <= k:
            return n
        slow, fast = k, k
        while fast < n:
            if nums[slow - k] != nums[fast]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

Conclusion

The two‑pointer pattern abstracts a simple rule that handles all variants of the problem, illustrating how a concise algorithm can solve a seemingly tricky interview question.