Skip to content

26. Remove Duplicates from Sorted Array

On LeetCode ->

Problem

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 it 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

Python solution

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

        for r in range(1, n):
            # Since nums is sorted, a new unique value differs
            # from the last kept one.
            if nums[r] != nums[w - 1]:
                nums[w] = nums[r]
                w += 1

        return w

img

Library alternative:

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

Comment on 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]