easyArrayTwo PointersTwo Pointers

Remove Duplicates from Sorted Array

easyTime: O(n)Space: O(1)

The shape of the problem

Remove duplicates from a sorted array in-place and return the count of distinct values. Only the first `count` positions need to be correct; anything after is ignored.

Signals to notice

sorted inputin-place compactioncount distinct values

Brute force first

Copy uniques into a new array, then copy back. O(n) time but O(n) extra space and defeats the in-place requirement.

The key insight

Because the array is sorted, duplicates are always adjacent. "New value" is equivalent to "different from the previous element" — a O(1) local test, not a O(n) search.

Trace it on nums=[1,1,2,2,3]

start w=1
r=1 nums[1]=1 == nums[0]=1  skip
r=2 nums[2]=2 != nums[1]=1  write → [1,2,2,2,3]  w=2
r=3 nums[3]=2 == nums[2]=2  skip
r=4 nums[4]=3 != nums[3]=2  write → [1,2,3,2,3]  w=3
return 3

What must stay true

At every iteration, `nums[0..write)` is the sorted list of distinct values seen in `nums[0..read]`.

Shape of the loop

if n == 0: return 0
w = 1
for r in 1..n-1:
  if nums[r] != nums[r-1]:
    nums[w] = nums[r]
    w += 1
return w

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting that `write=0` means element 0 is already "kept", so `write` should start at 1. Starting at 0 double-counts the first value.

Two Pointers Pattern