Remove Element

How it works

When there are few elements to remove, the previous approach does unnecessary copying. Instead, we can swap unwanted elements with elements from the end of the array. When we encounter the target value, we replace it with the last element and shrink the valid range by one. This minimizes write operations when removals are rare.

Steps

1. Initialize i = 0 as the current position and n as the effective length of the array.
2. While i < n:
   • If nums[i] equals val, replace it with nums[n-1] and decrement n (don't increment i since the swapped element needs checking).
   • Otherwise, increment i to move to the next element.
3. Return n as the count of valid elements.

Complexity

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

Things to watch for

Returning the Wrong Value

A common mistake is returning the length of the original array instead of the count of remaining elements. The problem asks for the number of elements that are not equal to val, which may be less than the original array length. Always return the write pointer position (k or n) that tracks how many valid elements exist after removal.

Incrementing the Pointer After a Swap

When using the swap-with-end approach (Two Pointers - II), forgetting to recheck the current position after swapping leads to missed removals. After replacing nums[i] with the last element, the swapped element might also equal val and needs to be checked. Only increment i when the current element is valid; otherwise, decrement n and keep i unchanged.

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        i = 0
        n = len(nums)
        while i < n:
            if nums[i] == val:
                n -= 1
                nums[i] = nums[n]
            else:
                i += 1
        return n

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0, n = nums.size();
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[--n];
            } else {
                i++;
            }
        }
        return n;
    }
};