Removing an Element in an Array In-Place
Tags: javascript, codenewbie, algorithms, leetcode
Published: 2020-06-09 14:44:29

Today's algorithm of the day is the [Remove Element Problem](https://leetcode.com/problems/remove-element/):
>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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice)). 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.

![A table. First row is of index values, `i`, in blue, going from 0 to 3. 0 is circled in green. Beneath each index is the corresponding value in the array [6, 4, 4, 5]. In the next row, the green circle is around i = 1, and under that a red line is drawn through the '4' at that index. In the next row, `i` only goes from 0 to 2, and now 2 is circled in green. The array beneath it is `[6, 4, 5]`.](https://dev-to-uploads.s3.amazonaws.com/i/3sfs54alpjpwgzqk0yok.png)

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]`.

![First row is index values written in blue. `i` goes from 0 to 3, and 0 is circled in green. Beneath each index is the corresponding value in the array, `[6, 4, 4, 5]`. Beneath the array is "i++ -> 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].](https://dev-to-uploads.s3.amazonaws.com/i/0ugmuwfb1z4qww9ujsic.png)

## 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.

```javascript
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`.

```javascript
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.


```javascript
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!