Solution: Two Pointers

The brute force is slow because of the shifting. Every duplicate causes a full shift of the tail, and that is $O(n)$ work to remove a single element.

Look again at what the problem asks for. We need the unique values packed at the front, and we need to return how many there are. The rest of the array is never read. So we do not have to move the duplicates anywhere. We only have to keep them out of the first k slots, and we can do that by writing the unique values over them as we go. Then there is no shifting.

I will walk you through it with an example first. Let’s say we have nums = [0,1,1,1,4]. The first and last elements are unique, and the middle three are duplicates of each other. We want to end up with nums = [0,1,4,_,_] and return k = 3.

Now imagine I have a friend helping me. In the diagrams below, the shaded slots are the ones we have already settled as unique. I start at the first element, 0. I send my friend to look at the next element, which is 1. This is different from 0, so I know 0 is unique.

┌───┬───┬───┬───┬───┐
│░0░│ 1 │ 1 │ 1 │ 4 │
└───┴───┴───┴───┴───┘
  ↑   ↑
 me  friend

Since 0 is unique, I move forward one slot, and now we are both looking at the same 1. This 1 is the second unique element we have found so far.

┌───┬───┬───┬───┬───┐
│░0░│░1░│ 1 │ 1 │ 4 │
└───┴───┴───┴───┴───┘
      ↑
   me & friend

Now I send my friend to look at the next element, which is also 1. This is a duplicate, so I stay where I am.

┌───┬───┬───┬───┬───┐
│░0░│░1░│ 1 │ 1 │ 4 │
└───┴───┴───┴───┴───┘
      ↑   ↑
     me  friend

I ask my friend to move to the next element, which is 1 again. Still a duplicate, so I stay where I am.

┌───┬───┬───┬───┬───┐
│░0░│░1░│ 1 │ 1 │ 4 │
└───┴───┴───┴───┴───┘
      ↑       ↑
     me      friend

I ask my friend to move again, and now they see 4. This is different from 1, so we are past the duplicates of 1, and 4 is a new unique value. I copy 4 into the slot right after mine. That slot held a 1, a duplicate, and overwriting it is safe, because the array beyond the first k slots is ignored. Now the first three slots hold the unique values [0,1,4], and the physical array looks like nums = [0,1,4,1,4].

┌───┬───┬───┬───┬───┐
│░0░│░1░│ 4 │ 1 │ 4 │
└───┴───┴───┴───┴───┘
      ↑           ↑
      me        friend

I move to the next element, which is now 4. I ask my friend to look at the next element, but there is not one, so we are done.

┌───┬───┬───┬───┬───┐
│░0░│░1░│░4░│ 1 │ 4 │
└───┴───┴───┴───┴───┘
          ↑       ↑
          me    friend

I am at index 2, and indexing starts at 0, so the number of unique elements is $2+1=3$. We return k = 3.

Between the two of us we found the unique elements and put them at the front of the array, and we did it with one pass. This is the two-pointer approach, and it is a common technique for problems on arrays.

Notice that I moved more slowly than my friend did. I only moved when a new unique value appeared. My friend moved on every step, because someone had to look at every element. So in code we call the two pointers slow and fast. The slow pointer marks the last slot of the unique prefix. The fast pointer scans through the array. Whenever fast finds a value different from the one at slow, we advance slow by one and copy the value there.

We copy the value, and we do not swap it. When I found the 4, I did not exchange it with the 1 that was in my next slot. I wrote over that 1, and I did not care where it went, because it was a duplicate and everything past the first k slots is ignored. A copy is one write. A swap would be three writes, and the two extra writes are not needed.

public static int removeDuplicates(int[] nums) {
  // Handle edge case
  if (nums.length == 0) {
    return 0;
  }

  int slow = 0;  // Last slot of the unique prefix
  // Fast pointer scans through array
  for (int fast = 1; fast < nums.length; fast++) {
    // Found a new unique element
    if (nums[fast] != nums[slow]) {
      slow++;                    // Move slow pointer
      nums[slow] = nums[fast];   // Place unique element
    }
  }

  // Return count of unique elements
  return slow + 1;
}

So what does this cost? There is one loop: fast runs from 1 to the end of the array, and the body is a comparison and at most one assignment, which is constant work. Constant work done $n$ times is $O(n)$. The method does not call anything else, so there is no call to follow this time.

On the same problem we went from $O(n^2)$ down to $O(n)$. At a million elements, the brute force needs days and this one needs about a second. We did not tune the brute force. We changed what the algorithm does, and that moved it to a different growth rate.