Remove Duplicates From Sorted Array

Keep each value of a sorted array once, at the front of the same array, and count them.

You are given an array of integers nums, sorted from smallest to largest, in which a value may appear several times. Remove the repeats in place, inside nums itself and without a second array, so that each value appears once and the values keep their order. Return k, the number of different values. The first k slots of nums must hold those values, and what is left in the slots after them does not matter.

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

The Idea

Picture the second example as a row of ten cards, in slots numbered 0 to 9: 0, 0, 1, 1, 1, 2, 2, 3, 3, 4. You want the different values, 0, 1, 2, 3 and 4, at the front of that same row. There is no second row to copy them into, and whatever ends up after them can stay.

Because the row is sorted, all copies of a value sit together. So to tell whether a card is a repeat, you only compare it with the last value you kept, not with every value kept so far. The 1 in slot 3 is a repeat because the last value kept is also 1.

But where do the kept values go, without a second array? They go into the same row, from the front. You can never have kept more cards than you have read, so writing stays at or behind reading. A slot is only written after its own card has been read.

So two markers move through the array in the same direction. One, fast, reads every card in turn. The other, slow, stays on the last value kept, and slots 0 to slow are the kept part. Look at the picture below.

The array 0, 0, 1, 1, 1, 2, 2, 3, 3, 4. Partway, at fast = 5, the kept part is 0, 1 and slow is on slot 1; the 2 at fast is copied into the next free slot, slot 2. At the end the first five slots hold 0, 1, 2, 3, 4, so k = 5, and the rest are leftovers.

In the top row, labelled "partway", fast is on slot 5 and reads 2. slow is on slot 1, so the kept part is 0, 1, and the last value kept is 1. The 2 is different, so it is new: slow moves to slot 2, the next free slot, and the 2 is copied there. The 1 that was in slot 2 was a repeat that fast had already read, so nothing is lost.

The bottom row is the array at the end. The first five slots hold 0, 1, 2, 3, 4, so k is 5, and the leftovers after them are cards nobody wrote over. Two markers that move the same way at different speeds are often called fast and slow pointers, one form of the two-pointer technique.

Solution Approach

Turning that idea into code means settling three things: where the two markers start, when the number at fast is kept, and how to get k at the end.

Shifting compared with two markers

What is the simplest way to remove a repeat in place? Move every number after it one slot left, the way deleting a letter in a text editor moves the rest of the line. Each shift can move almost the whole array, so with many repeats the work grows with the square of the array length. The two markers never shift: each number is read once and written at most once.

Where the markers start

Where should slow and fast start? The first number is always kept, because nothing comes before it that it could repeat. So slow starts on slot 0 and fast on slot 1. An empty array has no first number, so it is handled before the markers start, with k = 0.

Keeping or skipping a number

How does fast decide? If nums[fast] equals nums[slow], it is a copy of the last value kept, and it is skipped. Otherwise slow moves one slot right and nums[fast] is written there. In a sorted array a value that differs from the last one kept is larger, so it cannot have been kept earlier.

The count to return

How do we get k? slow is a slot number, and slot numbers start at 0. The kept part runs from slot 0 to slow, so it holds slow + 1 values.

Java Solution

The method removeDuplicates works in these steps:

  1. First, if nums is empty, return 0, since there is nothing to keep.
  2. Set slow to 0, so the first number is kept where it is.
  3. Move fast along the array with a loop, from slot 1 to the last slot.
  4. Inside the loop, compare nums[fast] with nums[slow]. When they differ, move slow one slot right and copy nums[fast] into nums[slow]. When they are equal, do nothing, and the loop moves fast on.
  5. After the loop, return slow + 1.

The main method runs both examples, one value repeated three times, an array with no repeats, a single number and an empty array, and prints k, the kept slots and the whole array for each.

Java
import java.util.Arrays;

public class RemoveDuplicatesFromSortedArray {

    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;                         // nothing to keep
        }
        int slow = 0;                         // nums[0..slow] holds the values kept so far
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {   // a value not kept yet
                slow++;
                nums[slow] = nums[fast];      // write it into the next free slot
            }
        }
        return slow + 1;
    }

    static void run(int[] nums) {
        int k = removeDuplicates(nums);
        System.out.println("k = " + k + ", kept " + Arrays.toString(Arrays.copyOf(nums, k))
            + ", whole array " + Arrays.toString(nums));
    }

    public static void main(String[] args) {
        run(new int[] {1, 1, 2});
        run(new int[] {0, 0, 1, 1, 1, 2, 2, 3, 3, 4});
        run(new int[] {2, 2, 2});
        run(new int[] {-3, -1, 0, 5});
        run(new int[] {7});
        run(new int[] {});
    }
}

Running it prints:

Output
k = 2, kept [1, 2], whole array [1, 2, 2]
k = 5, kept [0, 1, 2, 3, 4], whole array [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
k = 1, kept [2], whole array [2, 2, 2]
k = 4, kept [-3, -1, 0, 5], whole array [-3, -1, 0, 5]
k = 1, kept [7], whole array [7]
k = 0, kept [], whole array []

Look at the second line: the kept slots are [0, 1, 2, 3, 4], and the whole array still ends with 2, 2, 3, 3, 4, the leftovers from the bottom row of the picture. Example 1 behaves the same way on a small scale: [1, 1, 2] becomes [1, 2, 2], with the old 2 left in the last slot.

For [2, 2, 2], every number after the first is a copy of 2, so slow never moves and k is 1. [-3, -1, 0, 5] has no repeats, so each number is copied onto its own slot, the array comes out unchanged and k is 4. For the single number 7 the loop never runs, and k is 1.

The last line is the empty array, with k = 0. Without the length check at the top, the loop would not run either, and the method would return slow + 1, which is 1, for an array with no numbers in it.

The original implementation, RemoveDuplicatesFromSortedArray.java, is on GitHub.

Complexity

The method reads each number once and keeps only two slot numbers besides the array.

  • Time: O(n), for an array of n numbers, because fast walks over the n numbers once, and each step does one comparison and at most one write.
  • Space: O(1). The repeats are removed inside nums itself, and the only extra values are slow and fast.

When each value may appear up to twice, the same two markers work with a different check: see Remove Duplicates from Sorted Array II.