27. Remove Element

Remove Element

Problem Description

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted. 

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]

Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]

Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

 

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

Approach) Brute Force

In this solution, we loop through the numbers contained within the provided array, whilst checking each to see if it matches the number being removed. Whilst doing this, we also maintain a counter (j in the code), which tells us where in the original array we should place the next value.

The way this works is that if we start with an array of [1, 2, 3] and want to remove all occurrences of 2, we will look at 1, see that it is not being removed, and thus place it at the counter’s current value (which will be 0 to start with), leaving the array unchanged.
We’ll then look at 2, which we see does need to be removed, and so we move on to the next number without incrementing the counter. 

Finally when we reach 3, we see that it is not being removed, and so we place it at the counter’s position in the array (the counter is still set to 1 at this point), and increment the counter, giving us an array of [1, 3, 3] and a counter value of 2.
This then allows us to chop the array at the counter’s position, giving us a final array of [1, 3].

Code:

var removeElement = function (nums, val) {
    let j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[j++] = nums[i];
        }
    }

    //nums.length = j; // Chop the surplus values - not needed for LC submission
    return j;
};

Approach) Brute Force - Using Filter

Although not an accepted answer by LeetCode, I’d be remiss if I didn’t mention by far the simplest method of obtaining the desired result: .filter(). This method returns the filtered version of an array, and allows you to specify said filter using an arrow function, which makes for an incredibly neat solution:

Code:

var removeElement = function (nums, val) {
    nums = nums.filter((num) => num !== val);
    return nums.length;
};

Complexity 

Time Complexity

We are scanning the array only once, hence the time complexity will be O(n).

Space Complexity

We are not using any extra space, therefore, the space complexity should also be O(1).

Approach) Count 

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    if(!nums || nums.length < 1){
        return 0;
    }
    
    let count = 0;
    for(let i=0;i<nums.length;i++){
        if(i < nums.length && nums[i] == val){
            continue;
        }
        nums[count] = nums[i];
        count++;
    }
    return count;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #27. Remove Element

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!