26. Remove Duplicates from Sorted Array

EasyTwo PointersTwo pointers (read/write)Slow/fast in-place overwrite

Remove Duplicates from Sorted Array

Given a sorted integer array nums, remove duplicates in place so each unique value appears once, keeping their relative order. Return k, the number of unique elements, with the first k slots of nums holding those unique values (the rest may be anything).

Open official problem prompt ↗

In plain English

Compact a sorted array in place so each value survives exactly once, and report how many survive.

Picture it like this

Shelving sorted books: you keep a bookmark at the last unique title placed; as you flip through, any time a new title appears you slide it up next to the bookmark and move the bookmark forward.

Example

Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
Why: There are 5 distinct values 0,1,2,3,4; they are written into the front of the array and k = 5 is returned.

Constraints

1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 100nums is sorted in non-decreasing order

Pattern lesson

See the pattern, then code

Slow/fast in-place overwrite

↗

Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. A write pointer marks the end of the unique prefix; a read pointer scans ahead, and whenever it finds a value different from the last kept one, copy it into the write slot.

New words, made simpleKnow these before the algorithm

Write pointer (k): Index just past the last unique value; also the running count of uniques.
Read pointer (i): Index scanning forward through the original array.
In-place: Modifying nums directly without allocating a new array.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Set + rewrite

Extra memory and a needless sort violate the in-place, O(1) spirit of the problem.

Collect uniques in a set, sort them, and copy back.

Time O(n log n)Space O(n)

Best choiceSlow/fast pointers

Single pass, constant space, exploits the sorted order directly.

One pass comparing each element to the last kept value, overwriting in place.

Time O(n)Space O(1)

The rule we keep true

Invariant

nums[0:k] always contains the unique values seen so far, in order; nums[k-1] is the most recent unique value.

Why this is correct

Reasoning

Because the array is sorted, all copies of a value are contiguous, so comparing the current element only to nums[k-1] is enough to detect a genuinely new value; each new value is written exactly once, keeping the prefix both unique and ordered.

The algorithm in three movesSay these aloud before coding

1Keep the first element and set the write index k to 1

k=1 after keeping 0

2Scan i from 1 to the end

i=2 new value 1 -> nums[1]=1, k=2

3When nums[i] differs from nums[k-1], write it at nums[k] and advance k

final prefix [0,1,2,3,4], k=5

4Return k as the count of unique values

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnums[0]=0

2 · AskStart of unique prefix?

3 · Update statek=1, prefix [0]

4 · ResultKeep first element.

Key takeaway

Highlighted cells are the first occurrence of each unique value that gets copied to the front.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Empty guard
An empty array has zero unique values.
2
Lines 5Seed the prefix
The first element is always unique, so k starts at 1.
3
Lines 6-9Scan and overwrite
Compare to the last kept value; on a new value, place it at the write index and advance.
4
Lines 10Return count
k is exactly the number of unique values placed at the front.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element returns 1
All identical values return 1
All distinct values return n unchanged
Negative values within [-100,100] behave the same

Common beginner mistakes

Comparing nums[i] to nums[i-1] instead of nums[k-1] works here but is fragile if the pattern changes; the write-anchor comparison is the robust choice
Returning the array instead of the integer k
Trying to physically delete elements, which is unnecessary and slow

Check your understanding

Why is comparing against nums[k-1] correct even though k-1 may lag far behind i?

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two Pointers