Reference: LeetCode
Difficulty: Easy

My Post: Java Solutions with Explanation (One Pointer & Two Pointers)

Problem

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Note:

  • Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
  • The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Follow up: What happens when the elements to remove are rare?

Example: 

1
2
3
4
5
6
7
8
nums = [3,2,2,3], val = 3,
Return length = 2 ([2,2,3,3])

nums = [1], val = 1
Return length = 0 ([1])

nums = [0], val = 1
Return length = 1 ([1])

Analysis

One Pointer (better for many invalid elements)

Wow. It is very elegant!

1
2
3
4
5
6
7
8
9
3  2  2  3  val = 3
3  2  2  3  i = 0
lo
2  2  2  3  i = 1
   lo
2  2  2  3  i = 2
      lo
2  2  2  3  i = 3
      lo (length)

Check out the example above for why it is correct.

It is better when elements to remove are so many. So the if would be skipped often.

1
2
3
4
5
6
7
8
9
10
11
public int removeElement(int[] nums, int val) {
  int n = nums.length;
  int lo = 0;
  for (int i = 0; i < n; ++i) {
    if (nums[i] != val) {
      nums[lo] = nums[i];
      ++lo;
    }
  }
  return lo;
}

Time: $O(N)$
Space: $O(1)$

Two Pointers (rare invalid elements)

This approach is better when elements to remove are rare. So the if would be skipped often (check out the code later).

We use two pointers lo and hi to solve this problem. lo points to the current element we are examining; hi is the current position we want to put invalid element at. See the example below for detail.

1
2
3
4
5
val = 3
3  2  2  3
lo       hi
// Since the current element nums[lo] is invalid, we want to place it at where hi is currently pointing!
// After swapping, we decrease hi by 1, and it will point to a new position that we will put invalid element at.

Invariant: Consider two subarrays [0, lo) and (hi, n - 1]. The first one is for all valid elements and the second one is for all invalid elements we have examined. They won’t be changed in the future.

Someone may ask that by this swapping an invalid element nums[hi] = 3 would go to lo. It is okay, because if we do swapping we only update hi. However, lo stays where it used to be, so the invalid element will be considered in the next round.

Also, if lo does not point to an invalid element, we just increase lo by one to examine the next element.

lo < hi or lo <= hi:

It is important to decide to use lo < hi or lo <= hi as our loop condition. Here is a trick to find out which one is correct. (decided by base-case examination)

Consider the following example:

1
2
3
4
5
6
7
8
9
// A
   0  1
  [1]     val = 1
  lo
hi
// B
  [0]     val = 1
     lo
  hi

If we use lo < hi, the loop will not be executed and always return lo (0) as the length, which is not correct in case B. By observation, if we use lo <= hi, the above cases are handled very well and we have an invariant that lo will always be the resulting length.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int removeElement(int[] nums, int val) {
  int n = nums.length;
  int lo = 0, hi = n - 1;
  while (lo <= hi) {
    if (nums[lo] == val) {
      swap(nums, lo, hi);  // swapping
      --hi;
    } else {
      ++lo;
    }
  }
  return lo;
}

private void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

Time: $O(N)$
Space: $O(1)$