Topics › Arrays › Easy

Remove duplicates from sorted array

Easy TUF ID 47 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer array nums sorted in non-decreasing order. Remove the duplicates in place so that each distinct value appears exactly once, keeping the values in their original order. Return k, the number of distinct values. After the call, the first k positions of nums must hold those distinct values; whatever is left in positions k and beyond does not matter.

“In place” is the key requirement: the judge checks the original array, not a new one, and the follow-up expects O(1) extra memory.

Constraints: 1 ≤ n ≤ 3 × 10^4, -100 ≤ nums[i] ≤ 100. We also accept an empty array.

Example 1

nums = [1, 1, 2]
answer: k = 2, nums starts with [1, 2]          // the third slot can hold anything

Example 2

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
answer: k = 5, nums starts with [0, 1, 2, 3, 4]

Approach 1: Brute force, an ordered set

Intuition. “Each distinct value once, in ascending order” is exactly what an ordered set stores. Insert every element into a TreeSet; duplicates are discarded automatically, and iteration returns the values in ascending order, which for a sorted input is also their original order. Then copy the set back into the front of the array.

Algorithm.

1. Insert every element of nums into a TreeSet.
2. Iterate over the set, writing the values into nums[0], nums[1], ....
3. Return the size of the set.

static int bruteForce(int[] nums) {
    Set<Integer> unique = new TreeSet<>();
    for (int x : nums) unique.add(x);
    int i = 0;
    for (int x : unique) nums[i++] = x;             // TreeSet iterates in ascending order
    return unique.size();
}

Complexity. Time O(n log n): each of the n insertions into the balanced tree costs O(log n). Space O(n) for the set in the worst case (all values distinct).

This works even on unsorted input (it would then also sort the result), which is a hint that it ignores the strongest property we were given. A LinkedHashSet would make it O(n) time, but the O(n) extra memory remains, and the boxing of every int into an Integer makes it slow in practice.

Approach 2: Optimal, two pointers

Intuition. In a sorted array, equal values sit next to each other. So when scanning from left to right, a value is new exactly when it differs from the last distinct value we kept. We never need to look further back than that.

Use two indices:

• read scans every element once;
• write marks the position of the last distinct value kept so far.

The invariant is: nums[0..write] holds, in order, each distinct value among nums[0..read-1] exactly once, and nums[write] is the largest of them. When nums[read] differs from nums[write], it must be larger (the array is sorted), so it is a new value: advance write and copy it there. When it is equal, it is a duplicate: skip it.

Writing never damages unread data, because write is always strictly smaller than read; we only overwrite positions that have already been read.

Algorithm.

1. If nums is empty, return 0.
2. write = 0 (the first element is always kept).
3. For read = 1 to n - 1: if nums[read] != nums[write], do write++ and nums[write] = nums[read].
4. Return write + 1.

static int optimal(int[] nums) {
    if (nums.length == 0) return 0;
    int write = 0;                                  // nums[0..write] are the distinct values seen so far
    for (int read = 1; read < nums.length; read++) {
        if (nums[read] != nums[write]) {            // a new value: it can only differ from the last kept one
            write++;
            nums[write] = nums[read];
        }
    }
    return write + 1;
}

Dry run on Example 2 ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]):

The method returns write + 1 = 5.

Complexity. Time O(n): a single pass with constant work per element. Space O(1): two indices.

An equivalent formulation compares nums[read] with nums[read - 1] instead of nums[write]. In a sorted array both say “is this the first occurrence of its value?”. Comparing with nums[write] is slightly more robust because it is also the form you need for the follow-up “allow each value at most twice” (compare with nums[write - 1]).

Edge cases and pitfalls

• Empty array. There is no first element to keep; return 0 before touching nums[0].
• Single element. The loop does not run and the method returns 1.
• All values equal. write never moves, and the answer is 1.
• No duplicates. Every element is “kept”; each write copies a value onto itself, which is harmless.
• Negative numbers and extremes. Only equality comparisons are used, so Integer.MIN_VALUE and Integer.MAX_VALUE need no special care. The tests include both.
• Returning the wrong thing. The judge reads the first k slots using your returned k. Returning write instead of write + 1 drops the last distinct value.
• Unsorted input. The two-pointer method relies on duplicates being adjacent. For an unsorted array it would keep repeated values that are not next to each other; use a hash set there instead.

Related problems

• Remove duplicates from Sorted array is the same problem in the A2Z sheet.
• Remove duplicates from sorted DLL applies the same “compare with the last kept element” idea to a doubly linked list.
• Union of two sorted arrays also skips repeated values while walking sorted input with pointers.
• Contains Duplicate asks only whether any duplicate exists, on unsorted input.