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 after removing all occurrences of val.

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,_] //The underlined part is where the original array elements are not important.

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,,,_]

Steps

The key idea is to use two pointers:

1. k (slow pointer): This pointer keeps track of the index where the next non-val element should be placed. It starts at 0.
2. i (fast pointer): This pointer iterates through the array from index 0 to the end.

For each element nums[i] examined by the fast pointer:

• If nums[i] is not equal to val, we copy it to nums[k] and increment k. This effectively moves the non-val elements to the beginning of the array.
• If nums[i] is equal to val, we skip it; k remains unchanged.

After the loop finishes, k will represent the number of non-val elements in the array. The elements from index k onwards are irrelevant, as they will be removed (or ignored).

Explanation

The algorithm's efficiency stems from the in-place nature of the modification. We avoid creating a new array, reducing both space and time complexity. The slow pointer k acts as a boundary, separating the elements that need to be kept from those that should be discarded.

Code

function removeElement(nums: number[], val: number): number {
    let k = 0; // Slow pointer
    for (let i = 0; i < nums.length; i++) { // Fast pointer
        if (nums[i] !== val) {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
};

Complexity

• Time Complexity: O(n), where n is the length of the array. 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.