LeetCode 80: Remove Duplicates from Sorted Array II Solution in Python Explained

Problem Statement

LeetCode 80, Remove Duplicates from Sorted Array II, is a medium-level problem where you’re given a sorted integer array nums. Your task is to modify the array in-place to remove duplicates such that each element appears at most twice, returning the new length of the array. After the operation, the first (k) elements of nums should hold the result, where (k) is the new length, and the remaining elements can be anything.

Constraints

1 <= nums.length <= 3 * 10^4: Array length is between 1 and 30,000.
-10^4 <= nums[i] <= 10^4: Elements are within this range.
nums is sorted in ascending order.

Example

Input: nums = [1,1,1,2,2,3]
Output: 5
Explanation: After removing duplicates (allowing up to 2), nums = [1,1,2,2,3], length = 5.

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7
Explanation: Result = [0,0,1,1,2,3,3], length = 7.

Input: nums = [1,1,1]
Output: 2
Explanation: Result = [1,1], length = 2.

Understanding the Problem

How do you solve LeetCode 80: Remove Duplicates from Sorted Array II in Python? For nums = [1,1,1,2,2,3], modify it in-place to [1,1,2,2,3], allowing each number to appear at most twice, and return 5 as the new length. Since the array is sorted, we can process it sequentially, tracking duplicates. We’ll explore two approaches: a Two-Pointer with Count Solution (optimal and primary) and an Alternative with Single Pass Overwrite (intuitive and efficient). The two-pointer method runs in O(n) time with O(1) space, leveraging the sorted property.

Solution 1: Two-Pointer with Count Approach (Primary)

Explanation

Use two pointers: k (position to place the next valid number) and a counter to track occurrences of each number. Iterate through the array, allowing up to two instances of each number to be placed at k, incrementing k accordingly. The sorted nature ensures duplicates are consecutive.

Here’s a flow for [1,1,1,2,2,3]:

k=0, i=0, count=1, nums[0]=1
k=1, i=1, count=2, nums[1]=1
k=2, i=3, count=1, nums[2]=2
k=3, i=4, count=2, nums[3]=2
k=4, i=5, count=1, nums[4]=3
Result: [1,1,2,2,3], k=5

Handle Edge Case.

If length ≤ 2, return length.

Initialize Pointers.

k = 2 (first two elements are always valid), track count.

Iterate Array.

Compare with element two positions back, allow up to 2.

Update Array.

Place valid numbers at k, increment k.

Return New Length.

Step-by-Step Example

Example 1: nums = [1,1,1,2,2,3]

We need 5, nums = [1,1,2,2,3].

Goal: Remove duplicates, allow up to 2, return length.
Result for Reference: 5, nums = [1,1,2,2,3].
Start: nums = [1,1,1,2,2,3], k = 2.
Step 1: i = 2, nums[2] = 1.

nums[i-2] = nums[0] = 1, count ≤ 2, but already 2 ones, skip.

Step 2: i = 3, nums[3] = 2.

nums[1] = 1 ≠ 2, k = 2, nums[2] = 2, k = 3.

Step 3: i = 4, nums[4] = 2.

nums[2] = 2, count = 2, k = 3, nums[3] = 2, k = 4.

Step 4: i = 5, nums[5] = 3.

nums[3] = 2 ≠ 3, k = 4, nums[4] = 3, k = 5.

Finish: nums = [1,1,2,2,3,3], return k = 5.

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

We need 7, nums = [0,0,1,1,2,3,3].

Start: k = 2.
Step 1: i = 2, 1, nums[0] = 0, skip.
Step 2: i = 3, 1, nums[1] = 0, skip.
Step 3: i = 4, 1, nums[2] = 1, k = 2, nums[2] = 1, k = 3.
Step 4: i = 5, 1, nums[3] = 1, k = 3, nums[3] = 1, k = 4.
Step 5: i = 6, 2, nums[4] = 1, k = 4, nums[4] = 2, k = 5.
Step 6: i = 7, 3, nums[5] = 1, k = 5, nums[5] = 3, k = 6.
Step 7: i = 8, 3, nums[6] = 2, k = 6, nums[6] = 3, k = 7.
Finish: nums = [0,0,1,1,2,3,3], return 7.

How the Code Works (Two-Pointer with Count)

Here’s the Python code with line-by-line explanation:

def removeDuplicates(nums: list[int]) -> int:
    # Line 1: Handle edge case
    if len(nums) <= 2:
        return len(nums)

    # Line 2: Initialize k for position after first two elements
    k = 2

    # Line 3: Iterate from third element
    for i in range(2, len(nums)):
        # Line 4: Check if current number can be included
        if nums[i] != nums[k-2]:  # Compare with element two positions back
            nums[k] = nums[i]
            k += 1

    # Line 5: Return new length
    return k

Alternative: Single Pass Overwrite Approach

Explanation

Use a single pointer k to track the write position and a counter to allow up to two occurrences of each number. Overwrite the array with valid numbers, incrementing k only when placing a number, ensuring at most two duplicates.

Initialize Variables.

k = 0, count and prev for tracking.

Single Pass.

Count occurrences, write up to two.

Return Length.

Step-by-Step Example (Alternative)

For [1,1,1,2,2,3]:

Start: k = 0, count = 0, prev = None.
Step 1: 1, count = 1, nums[0] = 1, k = 1.
Step 2: 1, count = 2, nums[1] = 1, k = 2.
Step 3: 1, count = 3, skip.
Step 4: 2, count = 1, nums[2] = 2, k = 3.
Step 5: 2, count = 2, nums[3] = 2, k = 4.
Step 6: 3, count = 1, nums[4] = 3, k = 5.
Finish: nums = [1,1,2,2,3], return 5.

How the Code Works (Single Pass Overwrite)

def removeDuplicatesSingle(nums: list[int]) -> int:
    # Line 1: Handle edge case
    if len(nums) <= 2:
        return len(nums)

    # Line 2: Initialize variables
    k = 0
    count = 0
    prev = None

    # Line 3: Single pass through array
    for num in nums:
        if num != prev:
            count = 1
            nums[k] = num
            k += 1
        elif count < 2:
            count += 1
            nums[k] = num
            k += 1
        prev = num

    # Line 4: Return new length
    return k

Complexity

Two-Pointer with Count:

Time: O(n) – Single pass through array.
Space: O(1) – Only pointer variable.

Single Pass Overwrite:

Time: O(n) – Single pass.
Space: O(1) – Few variables.

Efficiency Notes

Both solutions are O(n) time and O(1) space, optimal for LeetCode 80. Two-Pointer with Count is simpler and leverages the sorted property directly, while Single Pass Overwrite is more explicit about counting duplicates, both meeting the in-place requirement.

Key Insights

Tips to master LeetCode 80:

Sorted Advantage: Use sorted order to track duplicates.
Two Limit: Allow exactly 2 occurrences.
In-Place: Overwrite array efficiently.

Additional Example

For nums = [1,1,2,2,2]:

Goal: 4, [1,1,2,2].
Two-Pointer: k=2, skip third 2, return 4.
Result: 4, nums = [1,1,2,2].

Edge Cases

Length ≤ 2: [1,1] – Return 2.
No Duplicates: [1,2,3] – Return 3.
All Same: [1,1,1,1] – Return 2.

Final Thoughts

The Two-Pointer with Count solution is a clean pick for LeetCode 80 in Python—efficient, in-place, and straightforward, with Single Pass Overwrite as a solid alternative. For a related challenge, try LeetCode 79: Word Search to switch to grid searching! Ready to dedupe? Solve LeetCode 80 on LeetCode now and test it with [1,1,1,2,2,3] or [0,0,1,1,1,1,2,3,3] to master duplicate removal. Dive in and trim that array!