Remove Duplicates From a Sorted Array

Given a sorted array, remove the duplicates in place so that each value appears once, and return the number of unique values k. The first k elements must hold the unique values in order; what is left after them does not matter. A Java array cannot shrink, so the method returns k and the caller reads only the first k elements.

LeetCode: 26. Remove Duplicates from Sorted Array

Example

Text

Input:  [2, 3, 3, 4, 5, 7, 7, 9]
Output: 6, array starts with [2, 3, 4, 5, 7, 9]

Brute force: collect the unique values

A TreeSet keeps one copy of each value, in sorted order. Copy them back to the front of the array.

Java

import java.util.Arrays;
import java.util.TreeSet;

public class Main {
    static int removeDuplicates(int[] nums) {
        TreeSet<Integer> unique = new TreeSet<>();
        for (int x : nums) {
            unique.add(x);
        }
        int k = 0;
        for (int value : unique) {
            nums[k++] = value;
        }
        return k;
    }

    public static void main(String[] args) {
        int[] a = {2, 3, 3, 4, 5, 7, 7, 9};
        int k = removeDuplicates(a);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));
    }
}

Output

6 [2, 3, 4, 5, 7, 9]

Time: O(n log n). Space: O(n). It ignores the fact that the input is already sorted.

Optimal: two pointers

In a sorted array, duplicates are next to each other. Keep write, the length of the unique prefix so far. A value is new exactly when it differs from the last value written, nums[write - 1].

Java

import java.util.Arrays;

public class Main {
    static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int write = 1;
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[write - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }

    public static void main(String[] args) {
        int[] a = {2, 3, 3, 4, 5, 7, 7, 9};
        int k = removeDuplicates(a);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));

        int[] b = {1, 1, 1};
        k = removeDuplicates(b);
        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(b, k)));

        int[] c = {};
        System.out.println(removeDuplicates(c));
    }
}

Output

6 [2, 3, 4, 5, 7, 9]
1 [1]
0

Time: O(n). Space: O(1).

In real code

When a new array is acceptable, IntStream.distinct() keeps the first occurrence of each value. It uses a hash set internally, so it also works on unsorted input, at O(n) extra space.

Java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] v = {2, 3, 3, 4, 5, 7, 7, 9};
        int[] unique = Arrays.stream(v).distinct().toArray();
        System.out.println(Arrays.toString(unique));
    }
}

Output

[2, 3, 4, 5, 7, 9]

Edge cases

Empty array: 0.
All values equal: 1.
Unsorted input: only adjacent duplicates are removed. Sort first, or use a HashSet.