LeetCode 26: Remove Duplicates from Sorted Array

Problem Restatement

We are given an integer array nums.

The array is already sorted in non-decreasing order.

We need to remove duplicate values in place so that every unique value appears only once. The relative order of the values must stay the same.

After modifying the array, return k, the number of unique values.

Only the first k elements matter. Values after index k - 1 can be ignored.

The official custom judge checks that k is correct and that nums[0:k] contains the expected unique values in order.

Input and Output

Function shape:

def removeDuplicates(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 1, 2]

The unique values are:

[1, 2]

So we modify the beginning of nums:

nums = [1, 2, _]

Return:

2

Example 2:

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

The unique values are:

[0, 1, 2, 3, 4]

So the first five positions should become:

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

Return:

5

First Thought: Brute Force

One simple idea is to build a new array of unique values.

Since the array is sorted, we can scan from left to right and append a value only when it differs from the previous value.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        unique = []

        for num in nums:
            if len(unique) == 0 or unique[-1] != num:
                unique.append(num)

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

        return len(unique)

This gives the right first k elements.

But it uses an extra array, so it does not follow the in-place requirement.

Problem With Brute Force

The problem asks us to modify nums directly.

Using another array makes the logic easy, but it spends extra memory proportional to the number of unique values.

We need to keep the same idea, but write the unique values back into nums while scanning.

Key Insight

Because nums is sorted, equal values are adjacent.

So we only need to compare the current value with the last unique value we have written.

Use two positions:

The section before write always contains the unique values found so far.

Algorithm

Start with:

write = 1

The first element is always unique because there is nothing before it.

Then scan from index 1 to the end.

For each index read:

if nums[read] != nums[write - 1]:
    nums[write] = nums[read]
    write += 1

The comparison checks whether the current value differs from the last unique value.

If it differs, we copy it to the next write position.

At the end, write is the number of unique values.

Correctness

At every step, the subarray nums[0:write] contains all unique values seen so far, in the same order as the original array.

When nums[read] equals nums[write - 1], it is a duplicate of the last unique value. Since the array is sorted, this duplicate belongs to the current run of equal values, so skipping it is correct.

When nums[read] differs from nums[write - 1], it is the first occurrence of a new value. Writing it to nums[write] appends exactly one copy of this new value to the unique prefix.

After the scan finishes, every unique value has been written once, and every duplicate has been skipped. Therefore, the first write elements of nums contain the required answer.

Complexity

Implementation

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        write = 1

        for read in range(1, len(nums)):
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1

        return write

Code Explanation

The variable write stores the length of the unique prefix.

write = 1

This is valid because the constraints say nums.length >= 1.

The loop starts at index 1 because index 0 is already part of the unique prefix.

for read in range(1, len(nums)):

When the current value differs from the last written unique value, we found a new unique value.

if nums[read] != nums[write - 1]:

We copy it into the next available position.

nums[write] = nums[read]

Then we grow the unique prefix.

write += 1

Finally, return the number of unique values.

return write

Testing

def check(nums: list[int], expected: list[int]) -> None:
    original = nums[:]
    k = Solution().removeDuplicates(nums)

    assert k == len(expected), (original, k, expected)
    assert nums[:k] == expected, (original, nums[:k], expected)

def run_tests():
    check([1, 1, 2], [1, 2])
    check([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4])
    check([1], [1])
    check([1, 2, 3], [1, 2, 3])
    check([-3, -3, -2, -1, -1, 0], [-3, -2, -1, 0])

    print("all tests passed")

run_tests()

Test meaning: