Remove Element

Problem Description

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k. To get accepted, you need to do the following things:

1. Modify the array nums such that the first k elements of nums contain the elements which are not equal to val.
2. Return k.

Examples

Constraints

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

Two Pointers for Array Compression

Instead of shifting all elements to the left upon finding the target value (which requires O(n²) time), you can track an active write pointer. As you scan through the array with a read pointer, copy non-target elements to the location of the write pointer and advance it. This reduces the time complexity to a linear pass with zero extra space.

Solution 1: Write Pointer Tracking

Use a write pointer to build the compressed array in-place.

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // write pointer
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        k = 0  # write pointer
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k

#include <vector>

class Solution {
public:
    int removeElement(std::vector<int>& nums, int val) {
        int k = 0; // write pointer
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
};

Complexity Analysis

• Time Complexity: O(n) where n is the number of elements in the input array. We scan each element once.
• Space Complexity: O(1) auxiliary space as the array is modified in-place.

Where It Breaks

If the target element to remove is sparse or not present, we end up performing redundant writes of elements to their original indices. However, this is still optimal under standard big O bounds.

Common Mistakes

• Incorrect pointer updates: Modifying the write pointer inside a block that executes for target values rather than non-target values.
• Off-by-one errors: Accessing indices equal to or exceeding the array bounds during pointers manipulation.

Frequently Asked Questions

Does the order of remaining elements matter? No, the problem statement specifies that the order of elements can be changed.

What happens if the array only contains target elements? The write pointer k will remain at 0, and the function will return 0. The first 0 elements of the array contain no occurrences of val, which is correct.

← All Problems