26. Remove Duplicates from Sorted Array

Reformulated question¶

Given a sorted list nums, remove duplicates in-place so each value appears once, keep order, and return the count of unique values.

Example:

nums = [0,0,1,1,2,2] -> k = 3, nums[:k] = [0,1,2]

Key trick¶

Use two pointers.

One pointer reads every value.
One pointer writes the next unique value.
Because the array is already sorted, a value is new iff it differs from the previous kept value.

Trap¶

Using extra structures like Counter, set, or a new list.
Forgetting the operation must be in-place.
Comparing with the previous original element instead of the previous kept unique element.
Mishandling edge cases like a single-element array.

Why is this question interesting?¶

It tests a core interview pattern:

in-place array compaction
two pointers
exploiting sorted input to get \(O(n)\) time and \(O(1)\) extra space

Solve the problem with idiomatic python¶

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        # Write index of the next unique value.
        write = 1

        # Start from the second element.
        for read in range(1, len(nums)):
            # Since nums is sorted, a new unique value differs from the last kept one.
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1

        return write

Library alternative:

None worth using here.
Built-ins like set or Counter break the intended \(O(1)\) extra space requirement.

Pytest test¶

import pytest

@pytest.mark.parametrize(
    "nums, expected_k, expected_prefix",
    [
        ([1], 1, [1]),
        ([1, 1], 1, [1]),
        ([1, 1, 2], 2, [1, 2]),
        ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], 5, [0, 1, 2, 3, 4]),
        ([-3, -3, -2, -2, -2, 0, 1, 1], 4, [-3, -2, 0, 1]),
        ([1, 2, 3], 3, [1, 2, 3]),
        ([2, 2, 2, 2], 1, [2]),
    ],
)
def test_remove_duplicates(nums, expected_k, expected_prefix):
    k = Solution().removeDuplicates(nums)
    assert k == expected_k
    assert nums[:k] == expected_prefix

Comment my solution¶

Your solution works for the shown examples, but it misses the main constraint.

Counter(nums) uses extra memory, so it is not in-place in the interview sense.
sorted(c.keys()) is unnecessary because the input is already sorted.
Time is still fine here, but space should be \(O(1)\), not \(O(n)\).
This problem is meant to be solved by overwriting the array with a write pointer.

## Solution

from collections import Counter


class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        c = Counter(nums)  # Counter({1: 2, 2: 1})
        uniq_numbers = sorted(c.keys())  # [1, 2]
        for idx, val in enumerate(uniq_numbers):
            nums[idx] = val
        return len(uniq_numbers)


## Test

import pytest


@pytest.mark.parametrize(
    "nums,expectedNums",
    [([1, 1, 2], [1, 2]), ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4])],
)
def test_remove_duplicate(nums, expectedNums):
    solution = Solution()

    k = solution.removeDuplicates(nums)

    assert k == len(expectedNums)
    for i in range(k):
        assert nums[i] == expectedNums[i]

Code¶

import pytest


class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        # With 1+ elements, the first one is always unique.
        write = 1

        # Scan the array once.
        for read in range(1, len(nums)):
            # Keep only values different from the last written unique value.
            if nums[read] != nums[write - 1]:
                nums[write] = nums[read]
                write += 1

        return write


@pytest.mark.parametrize(
    "nums, expected_k, expected_prefix",
    [
        ([1], 1, [1]),
        ([1, 1], 1, [1]),
        ([1, 1, 2], 2, [1, 2]),
        ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], 5, [0, 1, 2, 3, 4]),
        ([-3, -3, -2, -2, -2, 0, 1, 1], 4, [-3, -2, 0, 1]),
        ([1, 2, 3], 3, [1, 2, 3]),
        ([2, 2, 2, 2], 1, [2]),
    ],
)
def test_remove_duplicates(nums, expected_k, expected_prefix):
    k = Solution().removeDuplicates(nums)
    assert k == expected_k
    assert nums[:k] == expected_prefix

nums = [1, 1, 2]
k = Solution().removeDuplicates(nums)
print(k, nums[:k])  # 2 [1, 2]

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = Solution().removeDuplicates(nums)
print(k, nums[:k])  # 5 [0, 1, 2, 3, 4]