Remove Duplicates from Sorted Array

Problem in Plain English

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place so that each unique value appears once at the front of the array while keeping their relative order. Return k, the number of unique elements.

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place so that each unique element appears only once at the front of the array, keeping the relative order of the elements.

Return k, the number of unique elements. The first k entries of nums must hold those unique elements; the contents beyond index k - 1 do not matter.

Constraints

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

Examples

Example 1

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Two unique values exist, so k = 2 with nums[0] = 1 and nums[1] = 2; the entry after them is irrelevant.

Example 2

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Five unique values exist, so k = 5 with the front of the array reading 0, 1, 2, 3, 4.

Example 3

Input: nums = [7]
Output: 1, nums = [7]

The only value is already unique. The read/write loop does no work and returns k = 1.

Example 4

Input: nums = [-1, -1, -1, 0, 0]
Output: 2, nums = [-1, 0, _, _, _]

Three copies of -1 and two copies of 0 collapse to two distinct values. Only the prefix [-1, 0] is checked; the remaining three slots may hold any values.

Intuition

Sorted order makes repeated values consecutive. Keep the first value, then copy only the first value of each later run into the next open position. In [1, 1, 2], keep the first 1, skip the second 1, and write 2 into index 1. A read pointer visits the input while a write pointer counts the compacted prefix; the unused tail has no required contents.

Approaches

Using a Set

Solution Details

Reveal Using a Set: intuition, complexity, and code

Intuition

A set remembers which values have already appeared, so one left-to-right scan can collect each value the first time it shows up. Copying that collection back over the front of the array produces the required layout.

Step-by-Step Logic

Create an empty set seen and ordered list unique. Scan the original array from left to right before copying anything back.
For each value, test membership in seen. If it is new, add it to seen and append it to unique; otherwise skip it.
In Example 1, the first 1 is collected, the second 1 is skipped, and 2 is collected, leaving unique = [1, 2].
Copy each collected value to the same index at the front of nums. Write nums[0] = 1, then nums[1] = 2; the physical array becomes [1, 2, 2].
Return unique.length, here k = 2. Only nums[0] through nums[k - 1] are part of the output.

Why It Works

The set allows each distinct value into unique exactly once, while the left-to-right scan preserves first-occurrence order. Since the input is sorted, that list is also the required sorted unique sequence. Copying every list entry back produces exactly that sequence in the first k positions; the tail does not matter. This teaches the baseline but uses extra collections instead of the intended constant-space compaction.

Dry Run

Using a Set: variable states at each step
Phase	Read / write index	Value	seen after	unique after	nums after
Start	none	none	{}	[]	[1, 1, 2]
Read	0	1: new	{1}	[1]	[1, 1, 2]
Read	1	1: duplicate	{1}	[1]	[1, 1, 2]
Read	2	2: new	{1, 2}	[1, 2]	[1, 1, 2]
Copy	0	1	{1, 2}	[1, 2]	[1, 1, 2]
Copy	1	2	{1, 2}	[1, 2]	[1, 2, 2]
Return	none	k = 2	unchanged	[1, 2]	checked prefix [1, 2]; tail ignored

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the input length and u the number of unique values. The scan performs n expected constant-time set operations and copying makes u writes, giving expected O(n) time. The set and list each store u entries: O(u), bounded by O(n), extra space. Although the result is copied into the input, this baseline allocates extra storage. The bounded value domain caps u at 201, but the general method still needs collections.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int removeDuplicates(int[] nums) {5        Set<Integer> seen = new HashSet<>();6        List<Integer> unique = new ArrayList<>();7        for (int num : nums) {8            if (!seen.contains(num)) {9                seen.add(num);10                unique.add(num);11            }12        }13        for (int i = 0; i < unique.size(); i++) {14            nums[i] = unique.get(i);15        }16        return unique.size();17    }18}

Hints

Hint 1

Sorted order means every duplicate sits beside its original, so which neighbour reveals a new value?

Hint 2

One pointer could read every slot while a second pointer remembers where the next unique value goes.

Hint 3

The first element needs no test, so both pointers can start at index 1 with left counting unique values.

Edge Cases

All entries identical such as [1, 1, 1, 1], where the answer is 1 and only the front slot matters.
No duplicates such as [1, 2, 3, 4], where every value is written back onto itself and k = 4.
A single-element array such as [7], where the loop never runs and the answer is 1.

Common Mistakes and Interview Tips

Comparing nums[right] against nums[left], the write slot, instead of nums[right - 1], the previous read value.
Starting both pointers at 0, which treats the first element as its own duplicate and drops it.
Allocating a set or list misses the intended constant-extra-space solution even when the copied prefix is correct.
Returning the entire array or its original length instead of k fails the judge contract; only the first k slots are checked.
Deleting entries while scanning shifts later indices and can skip duplicates or make the scan quadratic.
Interview tip: explain the sorted-input assumption and the prefix invariant. An unsorted array does not make adjacent comparison sufficient.

Key Takeaway

On sorted input, a reader pointer plus a writer pointer compacts matching runs in one pass with constant extra space.