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 returned elements to be the "length" of the array.

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,4,0,3,,,_] 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.

Steps

1. Two Pointers: We'll use two pointers: k (representing the index of the next position to place a non-val element) and i (iterating through the array).

2. Iteration: We iterate through the array using i.

3. Comparison: If nums[i] is not equal to val, we copy the element to nums[k] and increment k.

4. Skipping val: If nums[i] is equal to val, we simply skip it (we don't do anything).

5. Return k: After the loop, k will hold the index of the next available position (which is also the new length of the array containing only elements not equal to val).

Explanation

The algorithm efficiently removes elements equal to val by overwriting them with elements that are not equal to val. The k pointer tracks the index of the next available position to place a non-val element. We iterate through the array; if an element is not val, we move it to the k position and increment k. The elements after index k are not considered part of the modified array.

Code

def removeElement(nums, val):
    k = 0  # Pointer for the next available position
    for i in range(len(nums)):
        if nums[i] != val:
            nums[k] = nums[i]
            k += 1
    return k

Complexity

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