Remove Element easy

Problem Statement

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-place, you must return the new length of the array after removing all occurrences of val.

Consider the number of elements in nums that are not equal to val as the new length.

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

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,3,0,4,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 1, 3, 0, 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).

Steps

1. Two Pointers: Use two pointers, k (for the new length) and i (for iteration). k will track the index where the next non-val element should be placed.

2. Iteration: Iterate through the array using i.

3. Comparison: If nums[i] is not equal to val, place it at index k and increment k. This effectively moves all non-val elements to the beginning of the array.

4. Return: After iterating through the entire array, k will hold the new length of the array containing only elements not equal to val. Return k.

Explanation

The algorithm uses a two-pointer approach to efficiently remove elements in-place. The k pointer keeps track of the "valid" part of the array—the section containing elements that are not equal to val. As the i pointer iterates, if it encounters an element that is not val, that element is moved to the kth position, extending the "valid" section. Elements beyond the kth position are irrelevant because they are effectively removed (though their values in the array remain unchanged). This ensures that the algorithm runs with O(1) extra space and modifies the input array directly.

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0; // Pointer for the new length
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[k] = nums[i]; // Move non-val element to kth position
                k++; // Increment new length
            }
        }
        return k;
    }
};

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 use only a constant amount of extra space for the pointers k and i.