Remove Element

Remove all instances of a value in-place from an array and return the new length.

TimeO(n)

SpaceO(1)

Given an integer array nums and an integer val, remove all occurrences of val in-place.

Return k, the number of elements remaining. The first k slots of nums must hold those elements in their original relative order. Elements beyond index k − 1 may be anything.

Constraints

Input: line 1 — space-separated integers; line 2 — val.
Output: print the first k elements as space-separated integers on one line (once per approach). If k = 0, print a blank line.
In-place: modify the input array — do not allocate a second full-sized buffer in the optimal approach.
Order: surviving elements keep their original relative order.

Input

3 2 2 3
3

Output

2 2

Explanation: Remove every 3 — two 2s remain at the front.

Naive Solution

Filter into a new list containing only values ≠ val, then copy back into nums[:k].

Simple and correct, but uses O(n) extra space for the auxiliary list.

// Filter into a new Vec, then copy back into the original buffer.
// Time: O(n)  Space: O(n)
fn remove_element_naive(numbers: &mut [i64], value: i64) -> usize {
    let new_nums: Vec<i64> = numbers.iter().copied().filter(|&n| n != value).collect();
    let len = new_nums.len();
    numbers[..len].copy_from_slice(&new_nums);
    len
}

Time — O(n)

One pass to filter, one pass to copy back → O(n).

Space — O(n)

The auxiliary list stores up to n kept values.

Space: the extra list duplicates every surviving element.

Next step: use two pointers to compact in-place — O(1) extra space.

Optimal Solution

Maintain two indices:

read — scans every position from 0 to n − 1.
write — next slot to place a kept value.

For each read:

If nums[read] != val, set nums[write] = nums[read] and increment write.
Otherwise skip (do not advance write).

Return write as k.

// read scans every index; write tracks the next slot for a kept value.
// Time: O(n)  Space: O(1)
fn remove_element_two_pointers(numbers: &mut [i64], value: i64) -> usize {
    let nums_length = numbers.len();
    let mut idx: usize = 0;
    let mut current: usize = 0;
    while current < nums_length {
        if numbers[current] != value {
            numbers[idx] = numbers[current];
            idx += 1;
        }
        current += 1;
    }
    idx
}

Time — O(n)

Single scan: each element visited once → O(n).

Space — O(1)

Only write and read indices — no auxiliary array.

Result: same k and same first-k values as the naive filter, with O(1) extra space.

Full source: Rust · Python