Soultion with intutions - #LeetCode 80 — Remove Duplicates from Sorted Array II

LeetCode 80 — Remove Duplicates from Sorted Array II

1) my first approach (Counter + new list) — why it fails the constraints

this code correctly computes the desired result but violates the problem requirements:

• Uses extra memory: Counter(nums) and the temporary list n both use O(n) space.
• Not strictly in-place: The problem requires modifying nums in-place with O(1) extra space.
• Order risk: Using a frequency map is unnecessary and could break the required stable relative order depending on iteration (avoid it).

from collections import Counter
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        c = Counter(nums)
        n = []
        for i in c:
            if c[i] >= 2:
                n.append(i)
                n.append(i)
            elif c[i] < 2:
                n.append(i)

        for i in range(len(n)):
            nums[i] = n[i]

        return len(n)

2) Optimal in-place solution — Two-pointer (O(n) time, O(1) space)

Keep at most 2 copies of each element. Use a write pointer p starting at index 2 and scan from index 2 onwards. If the current element is different from nums[p-2], it's safe to write it at nums[p].

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

        p = 2
        for i in range(2, len(nums)):
            if nums[i] != nums[p - 2]:
                nums[p] = nums[i]
                p += 1
        return p

Why this works: allowing two copies means the element at i is valid only when it differs from the element two positions before the write pointer. This ensures we never create a third copy.

3) Example walkthrough

Input: [1,1,1,2,2,3]

1. Start: p=2, array unchanged
2. i=2: nums[2]=1, nums[p-2]=nums[0]=1 → equal → skip
3. i=3: nums[3]=2, nums[p-2]=nums[0]=1 → different → write at nums[2]=2, p→3
4. i=4: nums[4]=2, nums[p-2]=nums[1]=1 → different → write at nums[3]=2, p→4
5. i=5: nums[5]=3, nums[p-2]=nums[2]=2 → different → write at nums[4]=3, p→5

Result (first p=5 elements): [1,1,2,2,3]

4) Comparison table

Approach	Time	Space	In-place?	When to use
Counter + rebuild (your code)	O(n)	O(n)	No	Not recommended — violates constraints
Two-pointer (recommended)	O(n)	O(1)	Yes	Use for in-place, interview-ready solution

5) Edge cases & tips

• Short arrays: if len(nums) <= 2, return len(nums).
• All same: e.g. [2,2,2,2] → result [2,2], return 2.
• Already valid: arrays with at most two copies of each number are unchanged.
• Interview tip: explain the invariant clearly: "nums[p-2] is the last element that would make a third duplicate — compare against it."