loading...
Cover image for Removing an Element in an Array In-Place

Removing an Element in an Array In-Place

alisabaj profile image Alisa Bajramovic ・5 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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.

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

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

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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

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.

 

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