Removing an Element in an Array In-Place

Today's algorithm of the day is the Remove Element Problem:

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

The problem should be solved using O(1) extra memory, so you cannot build an extra array. Also, as noted in the "Clarification":

Confused why the returned value is an integer but your answer is an array? Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

What this basically means is that you can't do something like count the number of instances that val appears in nums, and just return that count. You have to modify the inputted array.

I like this problem because modifying an array in place is a super useful thing to have in your back pocket. In this post, I'll discuss my approach, explaining what it means to remove elements "in place" and the dangers of doing so. Then, I'll code the solution using JavaScript.

Approaching the Problem

When removing elements in place, you'll often want to use .splice(). .splice() can alter an array in a few different ways, making it very versatile, and makes all of its modifications in place.

The term "in place" means to modify the inputted value, rather than creating a new one. Some methods, like .slice() return a copy of part of the inputted array, and do not modify the inputted array itself. In many instances, it's important to not modify the original array, such as if you don't want to risk messing with another function that relies on the inputted value. Other times, you do want to modify the inputted value, such as if you want to save a lot of space.

.splice() alters an array by removing or adding elements to it in place (you can read more about .splice and what it can do here). In this problem, we'll want to remove elements at certain indexes, which means we'll pass in two parameters into .splice -- the first is the index of the value we want to remove, and the second is the number 1, since we only want to remove one value at a time.

The other important thing to plan for when modifying arrays in place is that you'll have to account for removed elements when you're traversing through the array. To illustrate what I mean, let's look at an example.

Let's say we were given the array [6, 4, 4, 5], and were told to remove all instances of the number 4. We'd start at index 0. 6 does not equal 4, so we'd move onto index 1. The number at index 1 is 4, so we'd remove this element of the array. Because we didn't account for that removal, we'd now move on to index 2, therefore skipping over the second 4. The second 4 used to be at index 2, but because we removed an element in line, it moved back to index 1, and so our for loop missed it.

To account for this, every time we remove an element from the array, we can move the pointer back one step. In a typical for loop, every iteration through the loop, you increment i by 1 value. In this modification, before you enter the for loop again after removing an element, you'd decrement i by 1 value.

Using the same example as above, I'll demonstrate what that change would mean. We'll start at index 0 of the array [6, 4, 4, 5]. 6 isn't the value we're looking to delete, so we'll go on to the next index, index 1. 4 is the value we want to delete, and this time we'll also decrement the value of i, back to 0, and then continue in the for loop, so i = 1. Again, there's a value of 4 in this index, so we'll decrement i, so i = 0, and then the for loop will increment, so i = 1. We're left with the array [6, 5].

i = 1". In the next row, `i` still goes from 0 to 3, and now 1 is circled in green. Beneath that, the 4 from the array is crossed out in red. Beneath that is "i-- -> i = 0; i++ --> i = 1". In the next row, `i` goes from 0 to 2, and 1 is circled in green. Beneath that, the array is [6, 4, 5], and the 4 at index 1 is crossed out in red. Beneath that is, "i-- -> i = 0; i++ --> i = 1". In the last row, i goes from 0 to 1, and the 1 is circled in green. Beneath that is the array [6, 5]."/>

Coding the Solution

Once you lay out how you'll be approaching this problem, the solution does not take long to code.

We'll start by writing a for loop, going from index 0 to the end of nums, the inputted array.

function removeElement(nums, val) {
  for (let i = 0; i < nums.length; i++) {
    //...
  }
  //...
}

At every index, we'll check the value of nums at that index to see if it equals val. If it does, we know this element needs to be deleted, so we'll call .splice on the array, passing in the index, i, and 1, which means we'll delete one element at index i, in place. Also, to account for the in-place removals, as discussed above, once we've spliced that element away, we'll decrement i.

function removeElement(nums, val) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === val) {
      nums.splice(i, 1);
      i--;
    }
  }
  //...
}

Once the for loop is done checking and removing all of the elements of the array, we can return the length of the array with the removed elements.

function removeElement(nums, val) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === val) {
      nums.splice(i, 1);
      i--;
    }
  }
  return nums.length;
}

--
Please let me know if you have any questions about my approach, or if there are other ways you'd solve this problem!

Comments

[Vesa Piittinen]

Here are a couple of solutions that avoid the good old for loop just for the sake of avoiding it:

function removeItemInPlace(array, item) {
  let i
  while ((i = array.indexOf(item, i)) > -1) {
    array.splice(i, 1)
  }
  return array.length
}

I also named the function and variables differently, because element is easy to confuse with concepts like DOM elements or React elements, so I often prefer talking about array items instead.

You can optimize the above for a more straightforward readability:

function removeItemInPlace(array, item) {
  let i = array.indexOf(item)
  if (i === -1) return array.length
  do {
    array.splice(i, 1)
    i = array.indexOf(item, i)
  } while (i >-1)
  return array.length
}

The above code is structured so that if you ever decide to remove the mutation in place (which is often favored these days) and instead of length output the resulting array, you can have an optimization that simply returns the original array if no changes were done. It also makes use of do while loops which seem to be used quite rarely.

We can also use regular for loops in a slightly more unusual way if we remove the requirement for future immutability:

function removeItemInPlace(array, item) {
  for (let i = array.indexOf(item); i > -1; i = array.indexOf(item, i)) {
    array.splice(i, 1)
  }
  return array.length
}

Then finally the functionalish way to do this:

function removeItemInPlace(array, item) {
  return array.reduceRight((array, arrayItem, index) => {
    if (item === arrayItem) array.splice(index, 1)
    return array
  }, array).length
}

Although you'll probably scare those hipster coders who have put their faith on immutability! :D It is a bit weird how they want to waste so much processing power and effort to creating new arrays on every iteration of a loop just to "be sure" they don't do mutation. Anyway, I know I still would get super mega awesome bonus points for using reduceRight since you really don't see that one being used in the wild.

[Saloni Yadav]

The problem with splice is, it has an O(n) time complexity in worst case. Since this question doesnot demand the exact array and bothers not about what exists after the returned length of the array...
The following could be a better approach that splicing:

1. swap elements if you encounter val (push it to the back of the array)
2. just copy the non "val" values to the array index< return length