27. Remove Element

Intuition

The goal is to remove all occurrences of a specified value val from the array nums in-place. The challenge is to do this efficiently while maintaining the order of the remaining elements, although the order can be changed. The solution needs to modify the array in such a way that the first k elements are the ones not equal to val, where k is the number of elements not equal to val.

Approach

1. Initialize a variable res to 0. This will keep track of the position in the array where the next non-val element should be placed.
2. Iterate through each element n in the array nums.
3. If n is not equal to val, assign nums[res] to n and increment res.
4. After the loop, res will be the number of elements that are not equal to val.
5. Return res.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array nums. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) since we are modifying the array in place and not using any extra space that scales with the input size.

Code

C++

class Solution {
public:
    int removeElement(vector& nums, int val) {
        int res = 0;
        for (int n : nums) {
            if (n != val) {
                nums[res++] = n;
            }
        }
        return res;
    }
};

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        res = 0
        for n in nums:
            if n != val:
                nums[res] = n
                res += 1
        return res

Java

class Solution {
    public int removeElement(int[] nums, int val) {
        int res = 0;
        for (int n : nums) {
            if (n != val) {
                nums[res++] = n;
            }
        }
        return res;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function (nums, val) {
    let res = 0;
    for (let n of nums) {
        if (n !== val) {
            nums[res++] = n
        }
    }
    return res;
};