Remove Duplicates from Sorted Array

Problem

You are given an integer array nums sorted in non-decreasing order. Rearrange it in place so that each distinct value appears exactly once, keeping the distinct values in their original (sorted) order. Return k, the number of distinct values.

Only the first k slots of nums matter afterward — the judge reads nums[0..k-1] and compares against the expected distinct values; whatever sits beyond index k - 1 is ignored. You may not allocate a second array (O(1) extra memory required).

Examples

nums = [1,1,2] → k = 2, nums starts with [1,2] Two distinct values; the duplicate 1 is removed.
nums = [0,0,1,1,1,2,2,3,3,4] → k = 5, nums starts with [0,1,2,3,4] Five distinct values remain, in ascending order.
nums = [7] → k = 1, nums starts with [7] A single element has no duplicates.

Constraints

1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.
O(1) extra memory — expected O(n) time.

Think about it first

Hint 1

Because the array is sorted, all copies of a value sit next to each other. A value is a duplicate exactly when it equals its left neighbor.

Hint 2

Use one pointer to scan every element and another to mark where the next *new* value should be written. When do the two pointers move together, and when does only one move?

Hint 3

Keep `write` = length of the deduplicated prefix built so far. Scan with `read`; whenever `nums[read] != nums[write - 1]` (a value you haven't kept yet), copy it to `nums[write]` and bump `write`. Return `write`.

TL;DR

Slow/fast (write/read) two pointers over the sorted array — O(n) time, O(1) space.

Approach 1 — Brute force: dedupe through an auxiliary structure

Collect the distinct values into a separate container, then write them back.

def removeDuplicates(nums: list[int]) -> int:
    seen: list[int] = []
    for x in nums:
        if not seen or seen[-1] != x:
            seen.append(x)
    for i, x in enumerate(seen):
        nums[i] = x
    return len(seen)

(Using set + sorted also works but costs O(n log n) and forgets that the input is already sorted.)

Time: O(n).
Space: O(n) for seen.

The time is fine. The O(1) extra memory constraint rules it out: seen is exactly the second array the problem forbids.

Approach 2 — Slow/fast two pointers, in place

In a sorted array, duplicates are adjacent, so “is this a new value?” is a single comparison against the last value kept, nums[write - 1]. The output is a prefix of the input, and the write pointer can never overtake the read pointer, so overwriting is always safe.

def removeDuplicates(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

nums[0] is always kept, so both pointers start at 1. Invariant: nums[0:write] holds the distinct values among nums[0:read], in order.

Walkthrough on nums = [0,0,1,1,1,2,2,3,3,4]:

read	nums[read]	vs nums[write-1]	action	write	prefix so far
1	0	0 — equal	skip	1	`[0]`
2	1	0 — new	write	2	`[0,1]`
3	1	1 — equal	skip	2	`[0,1]`
4	1	1 — equal	skip	2	`[0,1]`
5	2	1 — new	write	3	`[0,1,2]`
6	2	2 — equal	skip	3	`[0,1,2]`
7	3	2 — new	write	4	`[0,1,2,3]`
8	3	3 — equal	skip	4	`[0,1,2,3]`
9	4	3 — new	write	5	`[0,1,2,3,4]`

Return write = 5; nums[0:5] = [0,1,2,3,4].

Time: O(n) — one comparison per element.
Space: O(1).

Approach 3 — Compare against the previous read element

The same algorithm can key off nums[read] != nums[read - 1] instead of the kept prefix: adjacent inequality in a sorted array also marks the first copy of each value. Note, though, that the prefix-based comparison of Approach 2 is the variant that generalizes cleanly to “keep at most K duplicates” (compare with nums[write - K]).

def removeDuplicates(nums: list[int]) -> int:
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write

Walkthrough on nums = [1,1,2]: read=1 → 1 == 1, skip; read=2 → 2 != 1, write nums[1] = 2, write = 2. Return 2, prefix [1,2].

For the follow-up “at most two of each” (LeetCode 80), swap the condition for nums[read] != nums[write - 2] — the prefix-based comparison of Approach 2 is the one that generalizes.

Time: O(n).
Space: O(1).

Common pitfalls

Calling nums.remove(x) or del nums[i] inside a loop — each deletion shifts the tail (O(n^2)) and skips elements as indices move under you.
Starting write at 0 and comparing nums[read] != nums[write - 1] — write - 1 = -1 wraps to the array’s last element in Python, silently corrupting the first decision.
Returning len(nums) or the deduped list instead of k — the judge needs the count, and the tail past k - 1 is deliberately garbage.
Assuming this works on unsorted input — adjacency of duplicates is what makes the single comparison sufficient; unsorted input needs a set (and different problem constraints).

Pattern takeaway

Slow/fast pointers turn “filter an array in place” into: write marks the end of the accepted prefix, read scans, and an element is copied down only when it passes the keep-test. When the input is sorted, membership tests collapse to a comparison with the last kept element — no hash set needed. Reach for this whenever the output is a subsequence of the input and order must be preserved: Remove Element, Move Zeroes, and the at-most-K-duplicates family are the same loop with a different if.