#26 Remove Duplicates from Sorted Array

frequently reported atBloomberg Microsoft Meta Google Amazon TCS

the problem

In plain words

Remove duplicates in place from a sorted array so each unique value appears once, keeping order. Return k, the number of unique values; the first k slots must hold them.

in nums = [1,1,2]

out 2, nums = [1,2,_]

in nums = [0,0,1,1,1,2,2,3,3,4]

out 5, nums = [0,1,2,3,4,_,_,_,_,_]

1 ≤ n ≤ 3·10⁴
Sorted non-decreasing

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (read / write)

In a sorted array duplicates are neighbours. Copy a value forward only when it differs from the last value you kept.

solutions

From brute force to optimal

Let a TreeSet remove duplicates and keep order, then write back.

Add all to a TreeSet.
Write the set back into nums.

timeO(n log n)

Each TreeSet insert is O(log n).

spaceO(n)

The set.

javajava.util.*

1class Solution {2    public int removeDuplicates(int[] nums) {3        Set<Integer> unique = new TreeSet<>();      // sorted + no duplicates4        for (int x : nums) unique.add(x);5        int i = 0;6        for (int x : unique) nums[i++] = x;7        return unique.size();8    }9}

write is the next free slot; copy when nums[read] ≠ nums[write−1].

write = 1.
For read in 1..n−1: if new value, nums[write++] = nums[read].
Return write.

timeO(n)

One pass.

spaceO(1)

In place.

javajava.util.*

1class Solution {2    public int removeDuplicates(int[] nums) {3        if (nums.length == 0) return 0;4        int write = 1;                               // nums[0] is always kept5        for (int read = 1; read < nums.length; read++) {6            if (nums[read] != nums[write - 1]) {     // a new value appears7                nums[write++] = nums[read];8            }9        }10        return write;11    }12}

in the room

How to say it in the interview

talk track

Confirm: the array is sorted, so all copies of a value sit next to each other.
Brute: a TreeSet drops duplicates, but that's O(n log n) time and O(n) extra space.
Optimal: read/write pointers — copy a value forward only when it differs from the last kept one, nums[write − 1].
State it: O(n) time, O(1) space. Test [1], [2,2,2] and an array with no duplicates.

traps

Starting write at 0: the first value is always kept, so start at 1.
Returning the array instead of k — the judge reads only the first k slots.
Comparing with nums[read + 1] and running off the end of the array.

what they ask next

Follow-ups

Allow each value at most twice (LC 80)?

Compare with nums[write − 2] instead of nums[write − 1].

before you submit

Edge cases to test

One element → k = 1.
All equal [2, 2, 2] → k = 1 and nums starts with [2].
No duplicates → k = n, nothing moves.
Negative values: [-3, -3, -1] → [-3, -1].

practise next