Remove Duplicates from Sorted Array

Given a sorted integer slice, remove duplicates in-place so that each value appears once. Return the new length k such that the first k elements contain the unique values in sorted order.

Why this is worth learning

Sortedness makes equal values contiguous. A run boundary is enough to recognize a new value; a hash set would solve a less constrained problem using unnecessary memory.

Before coding: one-minute experiment

For [-2,-2,-2,0,0,3], what is the output prefix, and how many writes after initialization are necessary?

Function signature

func RemoveDuplicatesSortedArray(nums []int) int

Inputs / outputs

• nums: sorted slice to modify in-place.
• Return: number of unique elements k; only nums[:k] is valid after the call.

Example

nums = [1,1,2,2,3]
After removal: nums = [1,2,3,_,_]
Return k = 3

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Because the array is sorted, duplicates are adjacent. Use a read/write pair:

Invariant: nums[:write] contains the unique values seen so far, in order.

Algorithm (step-by-step)

1. If the slice is empty, return 0.
2. Set write = 1 (the first element is always unique).
3. For read from 1 to len(nums)-1:
   • If nums[read] != nums[read-1], copy nums[read] to nums[write] and increment write.
4. Return write.

Correctness sketch

For an empty slice, returning zero is immediate. Otherwise the first value starts the compacted prefix. At each subsequent read index r, the prefix nums[:w] contains one copy of each run seen so far. If the current value differs from its predecessor, it begins the next run and is appended. Otherwise its run already has a representative. Writes are never ahead of the read index, so unread values remain available. When the scan ends, every run has exactly one representative, in sorted order.

Trace (hand walkthrough)

Example input:
nums = [1,1,2,2,3]
After removal: nums = [1,2,3,_,_]
Return k = 3

Walk:
- start write=1 with nums[0]=1
- read=1: nums[1]=1 equals nums[0]=1 -> skip
- read=2: nums[2]=2 differs from nums[1]=1 -> write nums[1]=2, write=2
- read=3: nums[3]=2 equals nums[2]=2 -> skip
- read=4: nums[4]=3 differs from nums[3]=2 -> write nums[2]=3, write=3

Pitfalls to avoid

• Off-by-one when the slice has length 0 or 1.
• Comparing to nums[write-1] vs nums[read-1] without thinking through the invariant.
• Returning a new slice instead of the new length.

Debugging lens

Exercise the empty slice, a single run, and several runs of unequal lengths. Comparing against a value outside the already-kept prefix is especially dangerous after introducing a different compaction rule.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• nums remains sorted because you only copy forward in order.

Reconstruction checkpoint

For [-2,-2,-2,0,0,3], what is the output prefix, and how many writes after initialization are necessary?

Return to Array & String · Module quiz