27. Remove Element Easy

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.

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

Approach

Input: An array nums and a value val

Output: Remove all elements equal to val in-place, and return the number of elements different from val

This is an in-place modification two pointers problem.

We can use one pointer i to scan the original array, and a pointer k to modify the original array and record how many numbers are not equal to val.

When we find nums[i] != val, we set nums[k] = nums[i] and advance the position of k by k += 1.

Finally, the position k represents the total number of values not equal to val.

Implementation

python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0  # Slow pointer, indicating the end index of the new array
        
        for i in range(len(nums)):  # Fast pointer, traverses every element
            if nums[i] != val:
                nums[k] = nums[i]  # Move valid elements to the front
                k += 1  # the length of the valid array increases
        
        return k  # Return the new length (number of valid elements)

javascript

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let k = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[k] = nums[i];
            k++;
        }
    }

    return k;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

27. Remove Element (English)27. 移除元素 (Chinese)