Solution: Brute Force

When solving problems like this, I also like to think about edge cases. For example:

• If the array has only one element, say nums = [5], then the output should be k = 1 and the array remains [5].

• If there are no duplicates, like nums = [1,2,3,4], then the output should be k = 4 and the array remains unchanged.

• If all elements are duplicates, like nums = [2,2,2,2], then the output should be k = 1 and the array becomes [2,_,_,_].

• If the array is empty, nums = [], then the output should be k = 0 and the array remains empty.

Now let’s think about the provided examples like nums = [0,0,1,1,1,2,2,3,3,4]. Are duplicates always adjacent? Could it be we get something like nums = [0,1,0,2,1]? The problem states that the array is sorted in non-decreasing order, and in a sorted array equal values have to be next to each other, because anything smaller comes before them and anything larger comes after. So duplicates are always adjacent. It means that for each element, I do not need to search the whole array to find out whether it is a duplicate. I can just compare it with the element right before it.

Okay, now let’s say I started with the first element, 0. Then I looked at the next element, which is also 0. I know this is a duplicate, and I must move it to the end of the array. But how do I do that? I could swap it with the last element, but the last element is the largest value, and putting it here would break the sorted order. The whole approach depends on the array staying sorted. Instead I can shift every element after the duplicate one slot to the left. That overwrites the duplicate and keeps the rest in order. It also leaves a junk slot at the end. Let’s work with this idea.

To see how this works, let’s use a smaller example: nums = [1,1,1,2,3,3]. We start at i = 1. The physical array always stays length 6. The thing that shrinks is the logical length n, which is how many slots still hold values we care about. Slots past the logical length hold leftover junk, and they are shaded in the diagrams below.

┌───┬───┬───┬───┬───┬───┐
│ 1 │ 1 │ 1 │ 2 │ 3 │ 3 │
└───┴───┴───┴───┴───┴───┘
      ↑
    i = 1

The element at i = 1 is 1, the same as the element at i - 1. That is a duplicate. We shift the tail left to overwrite it, reduce the logical length by one, and check the same index i again:

┌───┬───┬───┬───┬───┬───┐
│ 1 │ 1 │ 2 │ 3 │ 3 │░1░│
└───┴───┴───┴───┴───┴───┘
      ↑
    i = 1

Now i = 1 still points at a 1 that matches the element before it, so we shift and shrink again, staying at the same index:

┌───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 3 │░1░│░1░│
└───┴───┴───┴───┴───┴───┘
      ↑
    i = 1

This time i = 1 holds 2, which differs from the 1 before it, so we advance. At i = 2 we find 3, which differs from 2, so we advance again. At i = 3 we find another 3, which duplicates the one before it. One more shift-and-shrink gives us this, with the logical length down to 3:

┌───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │░1░│░1░│░3░│
└───┴───┴───┴───┴───┴───┘
              ↑
            i = 3

Now i is 3 and the logical length is 3, so i has advanced past the end and the loop stops. The first three slots hold the unique values [1, 2, 3] and every slot after them holds junk. We return k = 3.

Let’s make a helper function to shift elements to the left starting from a given index:

private static void shiftLeft(int[] nums, int start, int duplicate) {
  for (int i = start; i < nums.length - 1; i++) {
    nums[i] = nums[i + 1];
  }
  nums[nums.length - 1] = duplicate;  // or any value, since it will be ignored
}

Okay, now let’s use this helper function in our main function:

public static int removeDuplicates(int[] nums) {
  int n = nums.length;  // number of valid elements; shrinks as we remove duplicates
  for (int i = 1; i < n; i++) {
    if (nums[i] == nums[i - 1]) {
      shiftLeft(nums, i, nums[i]);
      n--;  // one fewer valid element
      i--;  // stay at the same index to check the new element
    }
  }

  return n;
}

Notice that this version handles our edge cases without any special casing. For an empty array, n starts at 0, the loop never runs, and we return 0. For a single-element array, n starts at 1, the loop again never runs, and we return 1. This works because n is initialized to the array’s length rather than to a fixed starting count.

Now what does this solution cost? It has the same shape as selectionSort. The method’s own loop looks linear, but the body calls another method that is not constant work. So we have to look at what that call costs.

shiftLeft iterates from start to the end of the array, so it is $O(n)$ in the worst case. removeDuplicates calls it once for every duplicate it finds. The worst case is an array where every element is a duplicate, like [2,2,2,2], because then we call shiftLeft on $n-1$ of the passes. An $O(n)$ helper called about $n$ times gives $O(n^2)$.

That is a lot of work for this problem. Every one of those shifts moves the whole tail of the array one slot to the left, and each shift only removes one element. On the next page we look at a solution that does not shift elements.