Remove Element

Problem

Given an integer array nums and a value val, remove every occurrence of val in place and return k, the number of elements that remain. After your function runs, the first k slots of nums must hold the surviving elements (in any order); whatever sits beyond index k-1 is ignored by the judge.

You may not allocate a second array — the point is O(1) extra memory.

Examples

• Input: nums = [3, 2, 2, 3], val = 3 → Output: k = 2, nums starts with [2, 2] Both 3s are removed; the two 2s remain in the first two slots.
• Input: nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2 → Output: k = 5, first five slots are a permutation of [0, 1, 3, 0, 4] Three 2s are removed; order of the keepers is free.
• Input: nums = [2], val = 3 → Output: k = 1, nums starts with [2] Nothing to remove.

Constraints

• 0 <= len(nums) <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

One pass, O(1) extra space is the target.

Think about it first

TL;DR

Two pointers (read/write compaction) — O(n) time, O(1) space.

Approach 1 — Brute force: repeated in-place deletion

The literal reading: find an occurrence of val, delete it (shifting everything after it left by one), repeat.

from typing import List


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == val:
                del nums[i]  # shifts the tail left: O(n)
            else:
                i += 1
        return len(nums)

Complexity: O(n²) time worst case (an array full of val triggers n deletions, each shifting O(n) elements), O(1) space.

n ≤ 100 makes this pass easily, but the interviewer wants the shift-free idea — and del on a Python list hides exactly the cost the problem is about.

Approach 2 — Two pointers: read/write compaction

The insight: you never need to delete anything — you only need the keepers packed at the front. Sweep a read pointer across the array and copy each keeper to a write pointer that only advances on keeps. Elements equal to val are simply never copied, so they end up overwritten or stranded past k. This is the standard two-pointer compaction (a.k.a. stable partition) that underlies Remove Duplicates, Move Zeroes, and friends.

from typing import List


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

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

Return k = 5; the first five slots hold [0, 1, 3, 0, 4] — matches the expected output, order preserved as a bonus.

Complexity: O(n) time, O(1) space. Every element is read once and written at most once.

Approach 3 — Two pointers from both ends (few removals)

The insight: if val is rare, Approach 2 still rewrites nearly every element. Instead, when the left pointer hits an offender, overwrite it with the last element and shrink the array’s logical end — the number of writes equals the number of removals, not the number of keepers. Order is not preserved, which the problem explicitly allows.

from typing import List


class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        end = len(nums)
        while i < end:
            if nums[i] == val:
                nums[i] = nums[end - 1]
                end -= 1          # re-examine index i: the moved element may be val too
            else:
                i += 1
        return end

Walkthrough on nums = [3, 2, 2, 3], val = 3:

1. i = 0: nums[0] is 3 → copy nums[3] (also 3) over it, end = 3. Array: [3, 2, 2, ·].
2. i = 0 again: still 3 → copy nums[2] (2) over it, end = 2. Array: [2, 2, ·, ·].
3. i = 0: 2 ≠ 3 → advance. i = 1: 2 ≠ 3 → advance. i = 2 = end → stop.
4. Return k = 2; first two slots are [2, 2]. Matches the expected output.

Complexity: O(n) time, O(1) space — but only about (number of removals) writes, ideal when removals are rare.

Common pitfalls

• In Approach 3, incrementing i after a swap: the element pulled from the back is unexamined and might itself be val (step 2 of the walkthrough is exactly that case).
• Returning the array instead of k — the judge reads the count from the return value and only inspects nums up to it.
• Reaching for nums.remove(val) in a loop or a list comprehension [x for x in nums if x != val] — the first is the hidden-shift brute force, the second allocates the forbidden second array (rebinding, not in-place).
• Empty input: both loops fall through naturally and return 0 — don’t special-case it.

Pattern takeaway

In-place filtering is a read/write two-pointer: the read pointer visits everything, the write pointer marks the boundary of “accepted so far”, and nothing is ever deleted — only overwritten. When order doesn’t matter and removals are rare, the swap-with-last variant trades stability for the minimum possible number of writes. These two compaction idioms cover the whole remove/dedupe/partition family.