Coding Challenge: Remove and Rearrange Array Elements In-Place in O(1) Memory and O(n) Time

Lately I've been trying to challenge myself by taking a stab at some common coding questions asked in software engineering job interviews. After years of working on apps you would think that this kind of thing comes easy, but software development in the modern age comes with a heavy side of Googling and lookup, so challenging your brain in this way to implement an algorithm or process from just its definition or description is good practice to keep you sharp.

Yesterday, I came across a question on LeetCode that was asking me to remove all elements of an array that match a certain value. Pretty simple right?

array - [value]

Wrong. There is a catch which means this above solution cannot be used. We are required to perform the removal in constant O(1) memory, so we can't create any new arrays, or modify the existing array. We are asked to do it in O(n) time as well. So we need to modify the array in place, while looping over its length max one time. Here's how I did it.

The exact working of the question looks like this:

- Given an array nums and a value val, remove all instances of that value in-place and return the new length.
- 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.

So we need to rearrange the elements of the input array by moving all unwanted values to the right side of it, then returning the length of the new array, which can be in any order. Seems like the best way to accomplish this is to iterate over the length of the array, swapping elements if they are a match with one on the right side, and keep track of the right edge of the array we will return. In code, this looks like:

# @param {Integer[]} nums
# @param {Integer} val
# @return {Integer}
def remove_element(nums, val)

  right = nums.length-1
  i = right
  while i >= 0
    if nums[i] == val
      # swap the element with whatever is on the right.
      nums[i] = nums[right]
      nums[right] = val
      right -= 1
    end
    i -= 1
  end

  return right + 1
end

Let's go over this line-by-line.

• Line 6: We need to keep track of the right edge index of the array we will use for the return value, i.e. the last index, hence right. This also indicates where we need to swap items with if we should come across a match with any other element. As we come across matches, we will decrement this boundary.
• Line 7: Setup an initial array index value i that keeps track of where we are in the array iteration. We are starting on the right side of the array and counting down, so i is initialized as right
• Line 8: Loop i over the length of the array, decrementing until we hit the first index.
• Line 9: Check to see if the number in the array at index i is the one we are looking for, val
• Line 11: It matched, so we need to move some things around. The value at index i is val, so we can immediately overwrite it with whatever the last value is of our "included" array, which is conveniently indicated by our right index.
• Line 12: Though it technically isn't asked of us, it bothered me that the returned array did not contain the same elements as before the method, so I wanted to move this matching value back outside the index of our "included" array and into a "removed" section, to the right of right.
• Line 13: We've added a new element to the "removed" section, and the "included" section's length shortened by 1, so let's decrement the right index to keep track of that.
• Line 15: Regardless of whether or not we found a match, we need to move on to the next index down the array, so let's decrement i to do that.
• Line 18: Finally, return the number of elements in the new array. Because right was a zero-based index value, we need to add 1 to it to get the number of elements up to that index.

Submitting this code to LeetCode passess all of their tests, and has the following stats:

Runtime: 32 ms, faster than 93.24% of Ruby online submissions for Remove Element.
Memory Usage: 9.3 MB, less than 100.00% of Ruby online submissions for Remove Element.

Onward to the next problem!

Was this page helpful for you? Buy me a slice of 🍕 to say thanks!