Remove Element Solution Explained – Step-by-Step

Easy Questions / Array

Remove Element

Easy

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. Return the number of elements in nums which are not equal to val.

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

Example

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.

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, 4, 0, and 3. The order can be changed.

Explanation

This problem is a classic example of the two pointers technique. We need to remove all occurrences of a specific value from an array in-place, meaning we cannot create a new array.

The key insight is that we can use two pointers:

k (slow pointer) - points to the position where the next non-val element should be placed
i (fast pointer) - scans through the array looking for elements to keep

For each element in the array, we check if it's not equal to val. If it's not equal, we place it at position k and increment k.

This approach works because we only care about elements that are not equal to val. The elements after position k-1 don't matter according to the problem statement.

Idea Map

Start

Initialize k = 0

For each nums[i]

If nums[i] ≠ val
Place at nums[k]
Increment k

Return k

Complexity Analysis

Time Complexity

O(n) - We traverse the array exactly once, where n is the length of the array. Each element is checked exactly once.

Space Complexity

O(1) - We only use a constant amount of extra space for the pointers, regardless of input size.

Code


def removeElement(nums, val):
Initializes the function `removeElement` which takes the array `nums` and the value `val` to remove as input.
    k = 0
Initializes pointer `k` to 0, which will track the position for the next non-val element.
    for i in range(len(nums)):
Loops through each index in the nums array.
        if nums[i] != val:
Checks if the current element is NOT equal to the value we want to remove.
            nums[k] = nums[i]
If the element should be kept, copy it to position k (overwrites if k < i).
            k += 1
Increments k to point to the next position for keeping elements.
    return k
Returns k, which is the count of elements not equal to val.


public int removeElement(int[] nums, int val) {
Initializes the function `removeElement` which takes the array `nums` and the value `val` to remove as input.
    int k = 0;
Initializes pointer `k` to 0, which will track the position for the next non-val element.
    for (int i = 0; i < nums.length; i++) {
Loops through each index in the nums array using a standard for loop.
        if (nums[i] != val) {
Checks if the current element is NOT equal to the value we want to remove.
            nums[k] = nums[i];
If the element should be kept, copy it to position k (overwrites if k < i).
            k++;
Increments k to point to the next position for keeping elements.
        }
End of the if statement.
    }
End of the for loop.
    return k;
Returns k, which is the count of elements not equal to val.
}
End of the function.


int removeElement(vector<int>& nums, int val) {
Initializes the function `removeElement` which takes a reference to the vector `nums` and the value `val` to remove as input.
    int k = 0;
Initializes pointer `k` to 0, which will track the position for the next non-val element.
    for (int i = 0; i < nums.size(); i++) {
Loops through each index in the nums vector using a standard for loop.
        if (nums[i] != val) {
Checks if the current element is NOT equal to the value we want to remove.
            nums[k] = nums[i];
If the element should be kept, copy it to position k (overwrites if k < i).
            k++;
Increments k to point to the next position for keeping elements.
        }
End of the if statement.
    }
End of the for loop.
    return k;
Returns k, which is the count of elements not equal to val.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Returning wrong value

Remember to return k, not the length of the array. The value k represents the count of valid elements after removal.

💡

Empty array

The algorithm correctly handles empty arrays by returning 0 since there are no elements to process.

✓

All elements equal to val

If all elements equal val, the algorithm returns 0 correctly since no elements are kept.

🔄

No elements equal to val

If no elements equal val, the algorithm returns the original array length as all elements are kept.

What is the Two Pointers Technique?

The two pointers technique is a powerful pattern where two pointers move through an array simultaneously. One pointer typically leads (fast pointer) while the other follows (slow pointer). This technique is commonly used for in-place array modifications, searching pairs in sorted arrays, and problems where you need to compare or process elements at different positions.

Learn more about two pointers →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Remove Element' problem on LeetCode.

AlgoExplained.dev