27. Remove Element - Explanation

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:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

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

Output: k = 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: k = 5, nums = [0,1,3,0,4,_,_,_]

Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

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
    }
}

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut k = 0;
        for i in 0..nums.len() {
            if nums[i] != val {
                nums[k] = nums[i];
                k += 1;
            }
        }
        k as i32
    }
}

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
    }
}

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut i = 0;
        let mut n = nums.len();
        while i < n {
            if nums[i] == val {
                n -= 1;
                nums[i] = nums[n];
            } else {
                i += 1;
            }
        }
        n as i32
    }
}

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.