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 remaining elements. After your function runs, the first k slots of nums must hold the surviving elements (in any order); anything beyond index k-1 is ignored by the judge.

Do not allocate a second array. Use 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

Target: one pass, O(1) extra space.

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 approach: find an occurrence of val, delete it (shifting everything after it left by one), and repeat.

from typing import List


def removeElement(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.

With n ≤ 100 this passes, but the interviewer is looking for the shift-free approach. Note that del on a Python list hides the very cost the problem is about.

Approach 2 — Two pointers: read/write compaction

The insight: you never need to delete anything; you only need the kept elements packed at the front. Sweep a read pointer across the array and copy each kept element to a write pointer that advances only on a keep. Elements equal to val are never copied, so they are overwritten or left stranded past k. This is the standard two-pointer compaction (stable partition) that also underlies Remove Duplicates and Move Zeroes.

from typing import List


def removeElement(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], matching the expected output, with order preserved.

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 a val, overwrite it with the last element and shrink the array’s logical end. The number of writes then equals the number of removals, not the number of kept elements. Order is not preserved, which the problem explicitly allows.

from typing import List


def removeElement(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 what has been accepted so far, and nothing is deleted, only overwritten. When order doesn’t matter and removals are rare, the swap-with-last variant trades stability for the minimum number of writes. These two compaction idioms cover the whole remove/dedupe/partition family.