27. Remove Element - Explanation

Description

You are given an integer array nums and an integer val. Your task is to remove all occurrences of val from nums in-place.

After removing all occurrences of val, return the number of remaining elements, say k, such that the first k elements of nums do not contain val.

Note:

The order of the elements which are not equal to val does not matter.
It is not necessary to consider elements beyond the first k positions of the array.
To be accepted, the first k elements of nums must contain only elements not equal to val.

Return k as the final result.

Example 1:

Input: nums = [1,1,2,3,4], val = 1

Output: [2,3,4]

Explanation: You should return k = 3 as we have 3 elements which are not equal to val = 1.

Example 2:

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

Output: [0,1,3,0,4]

Explanation: You should return k = 5 as we have 5 elements which are not equal to val = 2.

Constraints:

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

Topics

Array Two Pointers

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Understanding how to traverse and modify array elements by index
Two Pointers Technique - Using multiple pointers to track positions during array manipulation
In-Place Modification - Modifying an array without using extra space

1. Brute Force

Intuition

The simplest way to remove elements is to collect all the values we want to keep into a separate list.
We iterate through the array, skip any element that matches the target value, and store the rest.
Then we copy everything back into the original array.
This works but uses extra space proportional to the input size.

Algorithm

Create a temporary list tmp to store elements that are not equal to val.
Iterate through nums and add each element to tmp if it does not equal val.
Copy all elements from tmp back into the beginning of nums.
Return the length of tmp, which represents how many valid elements remain.

class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        tmp = []
        for num in nums:
            if num == val:
                continue
            tmp.append(num)
        for i in range(len(tmp)):
            nums[i] = tmp[i]
        return len(tmp)

public class Solution {
    public int removeElement(int[] nums, int val) {
        List<Integer> tmp = new ArrayList<>();
        for (int num : nums) {
            if (num != val) {
                tmp.add(num);
            }
        }
        for (int i = 0; i < tmp.size(); i++) {
            nums[i] = tmp.get(i);
        }
        return tmp.size();
    }
}

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        vector<int> tmp;
        for (int num : nums) {
            if (num != val) {
                tmp.push_back(num);
            }
        }
        for (int i = 0; i < tmp.size(); i++) {
            nums[i] = tmp[i];
        }
        return tmp.size();
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} val
     * @return {number}
     */
    removeElement(nums, val) {
        const tmp = [];
        for (const num of nums) {
            if (num !== val) {
                tmp.push(num);
            }
        }
        for (let i = 0; i < tmp.length; i++) {
            nums[i] = tmp[i];
        }
        return tmp.length;
    }
}

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        List<int> tmp = new List<int>();
        foreach (int num in nums) {
            if (num != val) {
                tmp.Add(num);
            }
        }

        for (int i = 0; i < tmp.Count; i++) {
            nums[i] = tmp[i];
        }

        return tmp.Count;
    }
}

func removeElement(nums []int, val int) int {
    tmp := []int{}
    for _, num := range nums {
        if num != val {
            tmp = append(tmp, num)
        }
    }
    for i := 0; i < len(tmp); i++ {
        nums[i] = tmp[i]
    }
    return len(tmp)
}

class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        val tmp = mutableListOf<Int>()
        for (num in nums) {
            if (num != `val`) {
                tmp.add(num)
            }
        }
        for (i in tmp.indices) {
            nums[i] = tmp[i]
        }
        return tmp.size
    }
}

class Solution {
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        var tmp = [Int]()
        for num in nums {
            if num != val {
                tmp.append(num)
            }
        }
        for i in 0..<tmp.count {
            nums[i] = tmp[i]
        }
        return tmp.count
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Two Pointers - I

Intuition

Instead of using extra space, we can overwrite unwanted elements in place.
We use a write pointer k that tracks where the next valid element should go.
As we scan through the array, whenever we find an element that is not equal to val, we write it at position k and move k forward.
At the end, everything before index k contains valid elements.

Algorithm

Initialize a pointer k = 0 to track the position for the next valid element.
Iterate through the array with index i:
- If nums[i] is not equal to val, copy it to nums[k] and increment k.
Return k as the count of valid elements.

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

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

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

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} val
     * @return {number}
     */
    removeElement(nums, val) {
        let k = 0;
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] !== val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
}

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
}

class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        var k = 0
        for (i in nums.indices) {
            if (nums[i] != `val`) {
                nums[k++] = nums[i]
            }
        }
        return k
    }
}

class Solution {
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        var k = 0
        for i in 0..<nums.count {
            if nums[i] != val {
                nums[k] = nums[i]
                k += 1
            }
        }
        return k
    }
}

Time & Space Complexity

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

3. Two Pointers - II

Intuition

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.

Algorithm

Initialize i = 0 as the current position and n as the effective length of the array.
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.
Return n as the count of valid elements.

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

public class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0, n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[--n];
            } else {
                i++;
            }
        }
        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;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} val
     * @return {number}
     */
    removeElement(nums, val) {
        let i = 0,
            n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[--n];
            } else {
                i++;
            }
        }
        return n;
    }
}

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int i = 0, n = nums.Length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[--n];
            } else {
                i++;
            }
        }
        return n;
    }
}

func removeElement(nums []int, val int) int {
    i, n := 0, len(nums)
    for i < n {
        if nums[i] == val {
            n--
            nums[i] = nums[n]
        } else {
            i++
        }
    }
    return n
}

class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        var i = 0
        var n = nums.size
        while (i < n) {
            if (nums[i] == `val`) {
                n--
                nums[i] = nums[n]
            } else {
                i++
            }
        }
        return n
    }
}

class Solution {
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        var i = 0
        var n = nums.count
        while i < n {
            if nums[i] == val {
                n -= 1
                nums[i] = nums[n]
            } else {
                i += 1
            }
        }
        return n
    }
}

Time & Space Complexity

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

Common Pitfalls

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.