{x}
blog image

Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • Return k.

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

Solution Explanation: Remove Element

The problem asks to remove all occurrences of a given integer val from an integer array nums in-place and return the number of elements remaining that are not equal to val. The order of the remaining elements doesn't matter.

Approach: Two Pointers (One Pass)

The most efficient approach utilizes a single pass through the array using two pointers implicitly. One pointer, k, acts as an index to track the position where the next element not equal to val should be placed. The other pointer is implicitly the iterator in the for loop that iterates through each element.

  1. Initialization: We initialize a variable k to 0. k will represent the index of the next position to place an element that is not equal to val.

  2. Iteration: We iterate through the array nums. For each element x:

    • Check for Equality: If x is not equal to val, we assign x to nums[k], effectively placing it in the correct position for the elements that will remain. We then increment k to move to the next position.

  3. Return Value: After iterating through the entire array, k holds the number of elements that are not equal to val. This is the value we return.

In essence: The algorithm efficiently overwrites elements equal to val with elements not equal to val, keeping the valid elements in the beginning of the array. Elements beyond k are irrelevant.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array nums. We iterate through the array once.
  • Space Complexity: O(1). We only use a constant amount of extra space to store the variable k.

Code Examples (with explanations inline)

Python:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0  # Initialize k to 0 (index for elements not equal to val)
        for x in nums:  # Iterate through the array
            if x != val:  # Check if the current element is not equal to val
                nums[k] = x  # If not, place it at index k
                k += 1  # Increment k to the next available position
        return k  # Return the number of elements that are not equal to val

Java:

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // Initialize k
        for (int x : nums) { // Enhanced for loop iterates through nums
            if (x != val) { // Check for inequality
                nums[k++] = x; // Place and increment k
            }
        }
        return k; // Return k
    }
}

C++:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0; // Initialize k
        for (int x : nums) { // Range-based for loop
            if (x != val) { // Check for inequality
                nums[k++] = x; // Place and increment k
            }
        }
        return k; // Return k
    }
};

The other languages (Go, TypeScript, Rust, JavaScript, C#, PHP) follow a similar structure, differing only slightly in syntax. The core logic remains the same efficient one-pass algorithm.