27. Remove Element


Problem Description

Given an array of integers nums and an integer val, the task is to remove all occurrences of val from nums, while performing the operations in-place. The elements can be rearranged, which means the order after removal does not need to be the same as the original order. The goal is to return the total count of elements that are not equal to val after this removal.

To solve this problem, you don't need to actually delete elements from the array; you only need to move elements that are not equal to val to the beginning of the array. Once you've done this, you can return the count of these non-val elements. The remaining elements in the array after this count are irrelevant for the problem and can be ignored.

Intuition

When approaching this problem, the key is to realize that since the order of the elements doesn't matter after removal, you can simply overwrite elements that equal val with elements that do not. By maintaining a variable k that tracks the number of valid elements (not equal to val), you can iterate through the array and every time you come across a valid element, you move it to the position indicated by k.

As you traverse the array with a loop, each time you find an element that isn't val, you place it at the kth index of the array and increment k. This simultaneously builds the subarray of valid elements at the front of the array while keeping track of its size. After the loop ends, every element before k is not val, and k itself represents the number of these valid elements, which is the final answer.

By applying this in-place method, you avoid extra space usage and complete the operation with a single pass through the array, resulting in an efficient solution.

Learn more about Two Pointers patterns.

Solution Approach

The implementation of the solution employs a straightforward yet efficient algorithm. It uses no additional data structures, relying only on the in-place modification of the input array nums.

The algorithm can be summarized in the following steps:

  1. Initialize a counter k to 0. This will keep track of the number of elements that are not equal to val, as well as the index where the next non-val element should be placed.
  2. Iterate through each element x in the array nums using a loop.
  3. In each iteration, check if x is not equal to val.
  4. If x is not equal to val, perform the following:
    • Assign the value of x to nums[k], effectively moving it to the index k of the array.
    • Increment the counter k by 1. This prepares k for the next valid element and also increments the count of non-val elements found so far.
  5. Once the loop is finished, all elements not equal to val are placed at the start of the array in the first k positions.
  6. Return the counter k, which represents the number of elements in nums that are not equal to val.

The simplicity of this algorithm lies in its single-pass traversal of the input array nums and the constant space complexity due to the in-place approach. Since we only use a simple counter and overwrite elements within the original array, we avoid the overhead of additional data structures.

The use of the counter as both a measure of valid elements and an index for placement makes this algorithm a fine example of efficient problem-solving with minimal operation.

Here is the Python implementation of the above approach, as presented earlier:

1class Solution:
2    def removeElement(self, nums: List[int], val: int) -> int:
3        k = 0
4        for x in nums:
5            if x != val:
6                nums[k] = x
7                k += 1
8        return k

By carefully setting up the k index and moving valid elements in place, the algorithm avoids unnecessary operations and concludes with the desired result, which is the size k of the new array that contains no occurrences of val.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's go through a small example to illustrate how the solution approach works. We are given the following array of integers, nums, and a value, val, that needs to be removed from nums:

1nums = [3, 2, 2, 3]
2val = 3

We want to remove all occurrences of 3. According to the solution approach, we use an index k to store the position where the next non-val element should be placed. Here's how the process unfolds:

  1. Initialize k to 0. The array nums looks like this:

    1nums = [3, 2, 2, 3]
    2k = 0
  2. Begin iterating over nums. The first element nums[0] is 3, which is equal to val, so we do nothing with it and move on.

  3. The second element nums[1] is 2, which is not equal to val. We place 2 at index k (which is 0), and then increment k:

    1nums = [2, 2, 2, 3] 
    2k = 1
  4. The third element nums[2] is also 2. We again put 2 at index k (which is now 1), and then increment k:

    1nums = [2, 2, 2, 3] 
    2k = 2
  5. The fourth and final element nums[3] is 3, which is equal to val. We do nothing with it.

  6. We have finished the loop, and now all elements not equal to val are placed at the start of nums. The array looks like this:

    1nums = [2, 2, 2, 3]

    Note that the last element (3) is irrelevant, as we only care about the first k elements.

  7. We return k, which is 2. This represents the number of elements in nums that are not 3 (our val). The first k elements of nums are the ones that count.

In this manner, the solution algorithm effectively removes all occurrences of val from nums and returns the count of non-val elements, all in a single pass through the array, without using extra space.

Solution Implementation

1class Solution:
2    def removeElement(self, nums: List[int], val: int) -> int:
3        # Initialize a new index for the updated list without the value 'val'
4        new_length = 0 
5
6        # Iterate over each number in the input list
7        for number in nums:
8            # If the current number is not the value to remove, update the list
9            if number != val:
10                # Assign the number to the new index location
11                nums[new_length] = number
12                # Increment the new length to move to the next index
13                new_length += 1
14
15        # Return the new length of the list after all removals are completed
16        return new_length
17
1class Solution {
2    // Method to remove all instances of a given value in-place and return the new length.
3    public int removeElement(int[] nums, int val) {
4        int newLength = 0; // Initialize a counter for the new length of the array
5        // Iterate over each element in the array
6        for (int num : nums) {
7            // If the current element is not the value to be removed, add it to the array's new position
8            if (num != val) {
9                nums[newLength++] = num;
10            }
11        }
12        return newLength; // The new length of the array after removing the value
13    }
14}
15
1#include <vector> // Include vector header for using the vector container
2
3class Solution {
4public:
5    // Function to remove all occurrences of a value from an array and return the new length
6    int removeElement(std::vector<int>& nums, int val) {
7        int newLength = 0; // Initialize the length of the new array after removal
8  
9        // Iterate through all the elements of the array
10        for (int element : nums) {
11            // Check if the current element is not the one to remove
12            if (element != val) {
13                // If it isn't, add it to the new array and increment the new array's length
14                nums[newLength++] = element;
15            }
16        }
17      
18        // Return the length of the array after removal
19        return newLength;
20    }
21};
22
1/**
2 * Removes all instances of a specified value from the array in-place and returns the new length of the array after removal.
3 * The order of elements can be changed. It doesn't matter what you leave beyond the new length.
4 *
5 * @param {number[]} numbers - The array of numbers from which we want to remove the value.
6 * @param {number} valueToRemove - The value to be removed from the array.
7 * @returns {number} The new length of the array after removing the specified value.
8 */
9function removeElement(numbers: number[], valueToRemove: number): number {
10    // Initialize the index for the placement of elements that are not equal to valueToRemove
11    let newLength: number = 0;
12  
13    // Iterate over each element in the array
14    for (const number of numbers) {
15        // If the current number is not equal to the value we want to remove, we place it at the newLength index
16        if (number !== valueToRemove) {
17            numbers[newLength] = number;
18            newLength++; // Increment the index for the next placement
19        }
20    }
21  
22    // Return the new length of the array after all removals
23    return newLength;
24}
25

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the code iterates over all elements in the array exactly once.

The space complexity of the code is O(1), indicating that the amount of extra space used does not depend on the size of the input array. The solution only uses a constant amount of extra space for the variable k.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄