Remove Element Algorithm: Leetcode Question 27
Hope everyone has had a productive first week of this brand new year. I myself have gotten many things checked off my to do list this week including spending more time on Leetcode. This time I’ll explain a more simple problem than last week’s problem which I feel could be valuable to read and understand in a short blog post such as this one to save you time. I will be solving this problem in JavaScript. Let’s dig in.
The Problem
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.
That is the official fine print of this question, but to simplify it further it really just means the following. After kicking all instances of the number we give you as a variable called val out of the array (nums), tell us how many numbers are left in the array.
An example of this: We have an array of [1, 2, 3, 3] and the value to remove is the number 3. 3 appears twice in this array and if we remove those instances, we will have an array that looks like the following [1, 2]. The question wants us to return the number of numbers left over as the answer, which is 2 numbers in this case.
The Solution
Using the JavaScript function keyword, we’ll name our function appropriately and pass in the two arguments the problem told us to pass in, the valued number to remove called value, and the array called nums.
I will use an example throughout this problem which I will write in italics under the steps to better understand what is happening. The sample array in this case will be [1, 2, 3, 3] and the value will be 3.
function removeElement(nums, val) {Next we will initialize the total length of numbers in the nums array, so that we can use it for the next part of our problem. We are assigning it to the length of the numbers -1 because all arrays start at 0 so we will always need a -1 to be one space behind the count of numbers to compensate for the 0.
function removeElement(nums, val) {
let length = nums.length - 1The reason why we need a variable to represent the length is because we want to make our while loop which is going to do all our logic go through the whole array. The first number in any array starts on index 0, the first one, so we are saying, “while the length of the number is at the first index perform the following logic.”
function removeElement(nums, val) {
let length = nums.length - 1
while(length >= 0){Now we are writing an if statement to check if the first number in the array is equal to the value we are trying to get rid of. If it is, then we need to remove it from the array because that is the number we are trying to remove and we ultimately are trying to be left with the numbers besides the removed number anyways so that we can count them in the end. The JavaScript shift method removes the first item of any array as shown below.
If the first element, 1, is equal to 3, then remove the first element which is 1. Remember our array is [1, 2, 3, 3]. It is not in this case so it will have to go into the else.
function removeElement(nums, val) {
let length = nums.length - 1
while(length >= 0){
if(nums[0] === val){
nums.shift()In all other cases, we can assume the number we are checking is not the number that we are supposed to remove. So we set a temporary variable to represent the first removed number and we push that number into the number array at the end because that’s what the JavaScript push method does; moves the number to the last place in the array.
Basically by doing this, all we are doing is making the second number become the first one once the first one moves to the end so that we can check the next number to see if we need to remove it.
The element 1 is the first element which is now assigned to the temporary variable. We are pushing the temporary variable to the end of the array so that the array changes from [1, 2, 3, 3] to [2, 3, 3, 1].
function removeElement(nums, val) {
let length = nums.length - 1
while(length >= 0){
if(nums[0] === val){
nums.shift()
} else {
let temporary = nums.shift()
nums.push(temporary)
}In the next line, we decrement the length so that it gets one number smaller. This way it doesn’t include the last number, which is the number want to keep in the array.
Decrement the length so that the array length doesn’t include 1 since we have already identified 1 is not the same as 3, the valued number.
function removeElement(nums, val) {
let length = nums.length - 1
while(length >= 0){
if(nums[0] === val){
nums.shift()
} else {
let temporary = nums.shift()
nums.push(temporary)
}
length--
}Eventually we are going to reach a point where all the numbers in the array have been checked, and whatever we have left are the numbers that are not instances of the valued number. This leaves us with the numbers we want to count left which is why we are returning the count (length) of numbers in the array at the end outside of the while loop logic.
Our array at the end will look like: [1, 2]. 1 and 2 will be left in the array because 2 will become the number checked. The loop will result in checking that 2 also doesn’t equal 3, the valued number. As mentioned, we are returning the count of numbers left, which will be 2; the final answer.
function removeElement(nums, val) {
let length = nums.length - 1
while(length >= 0){
if(nums[0] === val){
nums.shift()
} else {
let temporary = nums.shift()
nums.push(temporary)
}
length--
}
return nums.length
};Finally there is a curly bracket to close everything up. This algorithm is now complete to give you the number of elements left after removing all instances of the valued number. Hope you enjoyed kicking out all those pesky privileged numbers and counting how many are left standing as much as I did.
