Topics › Arrays › Easy

Remove duplicates from Sorted array

Easy TUF ID 2764 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array nums sorted in non-decreasing order. Remove the duplicates in place so that each distinct value appears exactly once, keeping the relative order, and return the number k of distinct values. After the call, the first k positions of nums must hold those distinct values in ascending order. Whatever sits in positions k .. n - 1 does not matter, and the array itself cannot be resized, which is why a count is returned instead of a new array.

Constraints: 0 ≤ n ≤ 3 × 10^4 on LeetCode, up to 10^5 on the sheet; values fit in a 32-bit signed integer.

Example 1

nums = [1, 1, 2]
k = 2, nums becomes [1, 2, _]        // the 1 appears once, then 2; the last slot is ignored

Example 2

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

Example 3

nums = [5, 5, 5, 5]
k = 1, nums becomes [5, _, _, _]

The guarantee that the array is sorted is what makes this easy: equal values sit next to each other, so a duplicate is always equal to the value right before it, and “have I seen this value before” collapses to “is it equal to the last value I kept”.

Approach 1: Brute force, a set that sorts and de-duplicates

Intuition. Ignore the sortedness and treat this as a generic de-duplication problem. A TreeSet keeps one copy of each value and iterates in ascending order, so pouring the array into it and pouring it back out yields exactly the desired prefix. This is the “I have a container that does the job” solution; it works, but it uses extra memory and does logarithmic work per element that the sorted order makes unnecessary.

Algorithm.

1. Insert every element into a TreeSet<Integer>.
2. Iterate over the set (ascending order) and write each value to nums[0], nums[1], ....
3. Return the number of values written.

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

Complexity. Time O(n log n): each insertion into a balanced tree costs O(log n). Space O(n) for the set in the worst case (all values distinct), plus boxing every int into an Integer.

A HashSet would bring the time down to O(n) on average but would lose the ordering, forcing a sort afterwards. Neither container exploits the one thing we know about the input.

Approach 2: Optimal, two pointers

Intuition. Maintain the invariant that nums[0..i] holds the distinct values discovered so far, in order. A second pointer j scans the rest of the array. Because the array is sorted, nums[j] is a new value exactly when it differs from nums[i], the last value we kept. When it is new, advance i and copy nums[j] into the freshly opened slot. When it is a duplicate, just move j on.

Why is it safe to overwrite nums[i + 1]? Because i < j always holds, and everything in nums[i + 1 .. j - 1] has already been examined and judged a duplicate. Those positions are dead; writing into them loses nothing.

Algorithm.

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

static int optimal(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int i = 0;                                   // nums[0..i] holds the distinct values found so far
    for (int j = 1; j < n; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

Dry run on nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

Return i + 1 = 5.

Complexity. Time O(n): j visits every index once and each visit is O(1). Space O(1): two indices, no copy.

The invariant is worth stating in full because it is the proof of correctness: before each iteration, nums[0..i] is the sorted list of distinct values among nums[0..j-1]. Initially (i = 0, j = 1) that is true. Each step preserves it, either by adding a genuinely new value or by skipping a duplicate. When j reaches n, nums[0..i] is the sorted list of distinct values of the whole array, so k = i + 1.

Edge cases and pitfalls

• Empty array. optimal must return 0 without reading nums[0]; the early return handles it. bruteForce naturally produces k = 0.
• Single element. [7] returns 1; the loop body never runs and i stays 0.
• All duplicates. [5, 5, 5, 5] returns 1. The if never fires, so only nums[0] survives.
• Already distinct. [1, 2, 3, 4] returns 4; the if fires every time and each element is copied onto itself (nums[i] = nums[j] with i == j), which is harmless.
• Returning i instead of i + 1. i is the index of the last kept element, so the count is one more. This off-by-one is the most common bug; test with [1, 1, 2] and expect 2.
• Comparing with nums[j - 1] instead of nums[i]. Both work here because duplicates are adjacent in a sorted array, but nums[i] states the invariant directly (“compare with the last value kept”) and is the form that survives when the problem changes to “keep at most two copies”.
• Unsorted input. The two-pointer method silently produces garbage on unsorted data, since it only compares neighbours. If sortedness is not guaranteed, sort first or fall back to a set.
• Negative values and extremes. Nothing changes; the method only uses !=. The tests include negatives and Integer.MIN_VALUE / Integer.MAX_VALUE.
• Expecting the tail to be cleared. The positions beyond k are unspecified. Do not assert on them, and do not waste time zeroing them unless the problem demands it.

Related problems

• Move Zeros to End uses the identical read-pointer / write-pointer pattern to compact non-zero elements.
• Union of two sorted arrays applies the same “skip if equal to the last written value” test while merging two arrays.
• Check if the Array is Sorted II is the previous problem on the sheet; sortedness is the property this one relies on.
• Second Largest Element is another problem where “distinct” is the word that matters.