LeetCode 80 - Remove Duplicates from Sorted Array II

LeetCode Problem 80

Difficulty: 🟡 Medium
Topics: Array, Two Pointers

Solution

Problem Understanding

This problem asks us to modify a sorted integer array in-place so that every unique value appears at most twice. Since the array is already sorted in non-decreasing order, duplicate values will always appear next to each other, which is a very important property that makes an efficient solution possible.

In simpler terms, we want to remove "extra" duplicates. A number may appear once or twice, but if it appears three or more times, all occurrences after the second must be removed. The operation must preserve the relative order of the remaining elements.

The phrase in-place is important. We are not allowed to allocate another array to store results. Instead, we must overwrite the existing nums array so that the valid result occupies the first k positions. Anything after index k - 1 is irrelevant and can contain any value.

The function should return k, the number of valid elements remaining after duplicate removal. The online judge only checks the first k elements of the array.

For example:

• [1,1,1,2,2,3] becomes [1,1,2,2,3], because the third 1 must be removed.
• [0,0,1,1,1,1,2,3,3] becomes [0,0,1,1,2,3,3], because only two 1s are allowed.

The constraints provide useful information about the scale of the problem:

• 1 <= nums.length <= 3 * 10^4 means the array can contain up to 30,000 elements.
• nums is guaranteed to be sorted in non-decreasing order.
• Values range between -10^4 and 10^4, but the actual value range is not especially important for the algorithm.

Since the array can be fairly large, repeatedly shifting elements or rebuilding arrays would be inefficient. The requirement for O(1) extra memory strongly suggests an in-place pointer-based solution.

Several edge cases are important to consider upfront. If the array has only one or two elements, no removal is ever necessary because every number is already allowed to appear at most twice. Arrays where all elements are identical, such as [5,5,5,5], can expose bugs in duplicate handling because only two copies should remain. Arrays with no duplicates at all should remain unchanged. Since the input is guaranteed to be sorted, we never need to search for duplicates across distant positions.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to build a new list while counting how many times each number has been included.

We iterate through the sorted array and track how many times the current number has appeared. If the count is less than or equal to two, we add the element to a result array. Otherwise, we skip it.

This works because the array is sorted, so duplicate elements are grouped together. We can easily count consecutive occurrences.

After constructing the filtered array, we copy the valid values back into nums and return the new length.

This approach is correct because it explicitly enforces the rule that each number may appear at most twice. However, it violates the problem's space constraint because it uses an additional array proportional to the input size.

Optimal Approach, Two Pointers

The key observation is that because the array is sorted, we can determine whether a value should be kept by comparing it with earlier values already written into the valid portion of the array.

Instead of building a separate array, we maintain a write pointer that tracks where the next valid element should be placed.

The important insight is this:

If we already allow at most two copies, then for any current number nums[i], we only need to compare it against the element two positions before the write pointer.

If:

nums[i] != nums[write_index - 2]

then adding this number will not exceed two occurrences, so we keep it.

Otherwise, we skip it because it would create a third duplicate.

This works because the valid prefix of the array is always maintained in sorted order.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses an extra array to store valid elements
Optimal	O(n)	O(1)	Uses two pointers and modifies the array in-place

Algorithm Walkthrough

1. Handle the simplest case first. If the array length is less than or equal to 2, return the length immediately because every element is already allowed.
2. Initialize a write pointer at index 2. We start here because the first two elements are always valid. Even if they are duplicates, two copies are permitted.
3. Iterate through the array starting from index 2.
4. For each current number nums[i], compare it with nums[write_index - 2].
5. If the values are different, it means adding the current element will not create more than two copies. Write the current element into nums[write_index] and increment write_index.
6. If the values are the same, skip this element because keeping it would create a third occurrence.
7. Continue until all elements have been processed.
8. Return write_index, which represents the length of the valid portion of the array.

Why it works

The algorithm maintains an important invariant:

At every step, the portion of the array from index 0 to write_index - 1 always contains a valid result where no element appears more than twice.

Because the array is sorted, duplicates appear consecutively. Comparing against write_index - 2 tells us whether the current number would become a third occurrence. If it matches that earlier element, we already have two copies and must skip it. Otherwise, it is safe to include.

Python Solution

from typing import List

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

        write_index = 2

        for read_index in range(2, len(nums)):
            if nums[read_index] != nums[write_index - 2]:
                nums[write_index] = nums[read_index]
                write_index += 1

        return write_index

The implementation begins by handling arrays of length two or smaller. Since every element may appear at most twice, no modification is needed in these cases.

The variable write_index tracks the position where the next valid element should be written. It starts at 2 because the first two elements are always valid.

The loop uses read_index to scan the array from left to right. For each element, we compare it with nums[write_index - 2]. This comparison determines whether including the current value would exceed the maximum allowed frequency of two.

If the values differ, we copy the current number into the write position and advance the write pointer. If they match, the element is skipped.

At the end, write_index represents the number of valid elements that remain.

Go Solution

func removeDuplicates(nums []int) int {
    if len(nums) <= 2 {
        return len(nums)
    }

    writeIndex := 2

    for readIndex := 2; readIndex < len(nums); readIndex++ {
        if nums[readIndex] != nums[writeIndex-2] {
            nums[writeIndex] = nums[readIndex]
            writeIndex++
        }
    }

    return writeIndex
}

The Go implementation follows the same logic as the Python version. Since slices in Go behave similarly to dynamic array views, we can modify nums directly in-place.

Go does not require special handling for integer overflow here because indices remain within array bounds. Empty slices are also handled naturally through the len(nums) <= 2 condition.

Worked Examples

Example 1

Input:

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

Initial state:

write_index = 2

read_index	nums[read_index]	nums[write_index - 2]	Action	Array State	write_index
2	1	1	Skip, third duplicate	[1,1,1,2,2,3]	2
3	2	1	Keep	[1,1,2,2,2,3]	3
4	2	1	Keep	[1,1,2,2,2,3]	4
5	3	2	Keep	[1,1,2,2,3,3]	5

Final result:

k = 5
nums = [1,1,2,2,3,_]

Example 2

Input:

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

Initial state:

write_index = 2

read_index	nums[read_index]	nums[write_index - 2]	Action	Array State	write_index
2	1	0	Keep	[0,0,1,1,1,1,2,3,3]	3
3	1	0	Keep	[0,0,1,1,1,1,2,3,3]	4
4	1	1	Skip	[0,0,1,1,1,1,2,3,3]	4
5	1	1	Skip	[0,0,1,1,1,1,2,3,3]	4
6	2	1	Keep	[0,0,1,1,2,1,2,3,3]	5
7	3	1	Keep	[0,0,1,1,2,3,2,3,3]	6
8	3	2	Keep	[0,0,1,1,2,3,3,3,3]	7

Final result:

k = 7
nums = [0,0,1,1,2,3,3,_,_]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once
Space	O(1)	Only a few variables are used

The time complexity is O(n) because every element is processed exactly once by the read pointer. No nested loops or repeated scans occur.

The space complexity is O(1) because the algorithm modifies the array in-place and only uses a constant number of extra variables, regardless of input size.

Test Cases

class Solution:
    def removeDuplicates(self, nums):
        if len(nums) <= 2:
            return len(nums)

        write_index = 2

        for read_index in range(2, len(nums)):
            if nums[read_index] != nums[write_index - 2]:
                nums[write_index] = nums[read_index]
                write_index += 1

        return write_index

solution = Solution()

nums = [1, 1, 1, 2, 2, 3]
k = solution.removeDuplicates(nums)
assert k == 5 and nums[:k] == [1, 1, 2, 2, 3]  # Example 1

nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
k = solution.removeDuplicates(nums)
assert k == 7 and nums[:k] == [0, 0, 1, 1, 2, 3, 3]  # Example 2

nums = [1]
k = solution.removeDuplicates(nums)
assert k == 1 and nums[:k] == [1]  # Single element

nums = [1, 1]
k = solution.removeDuplicates(nums)
assert k == 2 and nums[:k] == [1, 1]  # Two duplicates allowed

nums = [1, 1, 1]
k = solution.removeDuplicates(nums)
assert k == 2 and nums[:k] == [1, 1]  # Remove third duplicate

nums = [1, 2, 3, 4]
k = solution.removeDuplicates(nums)
assert k == 4 and nums[:k] == [1, 2, 3, 4]  # No duplicates

nums = [5, 5, 5, 5, 5]
k = solution.removeDuplicates(nums)
assert k == 2 and nums[:k] == [5, 5]  # All identical elements

nums = [-1, -1, -1, 0, 0, 1]
k = solution.removeDuplicates(nums)
assert k == 5 and nums[:k] == [-1, -1, 0, 0, 1]  # Negative numbers

nums = [1, 1, 2, 2, 3, 3]
k = solution.removeDuplicates(nums)
assert k == 6 and nums[:k] == [1, 1, 2, 2, 3, 3]  # Exactly two duplicates

nums = [1, 1, 1, 2, 2, 2, 3, 3, 3]
k = solution.removeDuplicates(nums)
assert k == 6 and nums[:k] == [1, 1, 2, 2, 3, 3]  # Multiple groups with excess duplicates

Test	Why
[1,1,1,2,2,3]	Validates the first provided example
[0,0,1,1,1,1,2,3,3]	Validates the second provided example
[1]	Minimum input size
[1,1]	Two duplicates should remain
[1,1,1]	Third duplicate should be removed
[1,2,3,4]	No duplicates present
[5,5,5,5,5]	All elements identical
[-1,-1,-1,0,0,1]	Handles negative numbers
[1,1,2,2,3,3]	Exactly two duplicates already valid
[1,1,1,2,2,2,3,3,3]	Multiple repeated groups

Edge Cases

Arrays with fewer than three elements

Arrays of size one or two are important because the algorithm starts from index 2. A careless implementation could accidentally access invalid indices and crash. Since at most two copies are allowed, these arrays are already valid. The implementation safely returns the original length immediately.

Arrays where all elements are identical

An input like [7,7,7,7,7] is a common source of bugs because every element after the second must be skipped. Incorrect pointer handling can accidentally retain too many duplicates or overwrite values incorrectly. The comparison against write_index - 2 guarantees that once two copies are stored, all later identical values are ignored.

Arrays with no duplicates

Inputs such as [1,2,3,4,5] should remain unchanged. Some implementations accidentally overwrite values unnecessarily or mishandle pointer increments. In this solution, every comparison succeeds because adjacent unique values differ, so all elements are preserved and the original order remains intact.

Multiple duplicate groups

An input like [1,1,1,2,2,2,3,3,3] tests whether the algorithm correctly resets duplicate tracking between different values. Since the solution only compares against the valid prefix of the array, each number is independently limited to two occurrences without interfering with other groups.