Remove Element

We are given an array of integers nums and a specific integer val which we must remove in-place (this means without duplicating the array etc.; we modify it “in-place”). k elements are not val and first k items in our resulting array will be these elements. The elements after can be anything, and the array can be any length so long as it is greater than or equal to k.

Planning

Consider the following case:

nums = [3, 1, 4, 3]
val = 3

There are 2 items in nums not equal to val (3). This means that our resulting array can be [4, 1], [1, 4, 3, 3], [4, 1, _, _], or any other array so long as the first 2 items are [1, 4] (in any order).

A good way to think about what happened is that we shifted all the non-val elements to the front and collected all the val elements at the end of the array.

This swap with two pointers, one traversing front-to-rear and the other rear-to-front. We’ll call the front pointer f and the rear pointer r. Each time f is equal to val, we’ll swap f with r. f will move up the array to check each element.

[3, 1, 4, 3]
 f        r

[3, 1, 4, 3]
    f  r

[3, 1, 4, 3]
    r  f

[3, 1, 4, 3]
 r        f

Wait, why didn’t our elements get swapped? We have two issues:

• Our rear pointer begins at the last element, which also happens to be equal to val. Let’s make sure r is not val, moving down if it is.
• r keeps traversing forward past f! If we successfully swapped each element (which we didn’t), everything behind r should be just a bunch of vals or some other useless value. We can stop where f meets r.

Let’s try again, following our new conditions:

[3, 1, 4, 3] #r starts from the first non-val element in reverse order
 f     r

[4, 1  3, 3] #we can stop since f meets r
    f  r

Our output [4, 1, 3, 3] satisfies the conditions, since the first two items are not val (there are two non-val items in total).

We can examine the behaviour of our simple rules one more time with the input nums = [0, 1, 4, 2, 3, 0, 4, 2], val = 2:

[0, 1, 4, 2, 3, 0, 4, 2] #r starts at 4 since 2 == val
 f                 r

[0, 1, 4, 2, 3, 0, 4, 2] #f moves forward 
       f           r

[0, 1, 4, 2, 3, 0 ,4, 2] #f will swap with r since f == 2
          f        r

[0, 1, 4, 4, 3, 0, 2, 2] #f meets r; stop
             f  r

This seems to have worked again! Let’s translate this into code.

Code

We will define a function removeElement with an inputs nums (a list of integers List[int]) and val (an integer int). This function will return the number of items (an integer int) that are not equal to val in nums.

def removeElement(nums: List[int], val: int) -> int:

Note that we are using type hints, which are not necessary.

Let’s assign our two pointers f and r, which will be the index positions in the array of the item that we are checking.

• Our front pointer f starts at 0, which is the beginning index in python.
• Our rear pointer r starts at the index last element, which is equal to the length of nums less one. This is because our first index is 0.

	f = 0
	r = len(nums) - 1

We now need to check our first condition, that the element at r is not equal to val, since we don’t want to be swapping in the same value. We can achieve this with a while loop that moves up the array until the element at r is not equal to val.

• One other thing: we must make sure that r is at or above zero. Otherwise, we would continue to traverse the array using reverse indices.

	while r >= 0 and nums[r] == val:
		r -= 1

Now we can get swapping! We will use another while loop that checks each item at our f pointer, making a swap if it’s equal to val. This loop will stop once f meets r, so f must be less than or equal to r.

• If we find val, we make the swap.
• r moves down the array since we know that we can’t swap one val with another.

	while f <= r:
		if nums[f] == val:
			nums[f] = nums[r]
			nums[r] = val
			r -= 1
		else:
		 f += 1

Why do we move our pointer f outside of the if clause? Well, we only checked that we didn’t swap with val when we initially set the position of r. What if the following element was equal to val? When f is incremented outside, we are able to try another swap with the next value and so on, until we find one that’s not val, satisfying our condition.

Finally, we can finish our function by returning f, which happens to be the number of non-val elements.

	return f

Let’s put this code together:

def removeElement(nums: List[int], val: int) -> int:
	f = 0
	r = len(nums) - 1
	
	while r >= 0 and nums[r] == val:
	r -= 1
	
	while f <= r:
		if nums[f] == val:
			nums[f] = nums[r]
			nums[r] = val
			r -= 1
		else:
		 f += 1
	 
	return f