Remove Element

Remove all occurrences of a target value from an integer slice in-place. Return the new length k such that the first k elements of nums are the kept values.

We will preserve the relative order of the remaining elements (stable removal). This makes the behavior deterministic and easier to reason about.

Why this is worth learning

This course requires stable compaction: the order of surviving values is part of the contract. Swapping a removed value with the tail solves a different, unstable variant.

Before coding: one-minute experiment

For nums=[3,1,3,2,1] and val=3, what length and valid prefix must be returned?

Function signature

func RemoveElement(nums []int, val int) int

Inputs / outputs

• nums: the slice to modify in-place.
• val: the value to remove.
• Return: the number of kept elements k. Only nums[:k] is valid after the call.

Example

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

After removal (stable): nums = [2,2,_,_]
Return k = 2

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i], val <= 1_000_000_000

Core idea (near-solution)

Use read/write pointers:

• read scans each element once.
• write marks the next index to place a kept value.

Invariant: all indices < write are kept values in the correct (original) order.

Algorithm (step-by-step)

1. Initialize write = 0.
2. For each read from 0 to len(nums)-1:
   • If nums[read] != val, copy it to nums[write] and increment write.
3. Return write.

Correctness sketch

Before reading position r, nums[:w] is exactly the non-target subsequence of the original prefix ending before r, and w<=r. A target contributes nothing. A surviving value is appended at w, preserving encounter order; the write cannot affect any position after r. Thus the invariant extends to r+1. After all n original positions are read, nums[:w] contains precisely all survivors. Only that prefix is specified; the suffix is not an output and need not be cleared.

Trace (hand walkthrough)

Example input:
nums = [3,2,2,3], val = 3

After removal (stable): nums = [2,2,_,_]
Return k = 2

Walk:
- read=0 (3): skip (val), write=0
- read=1 (2): keep -> nums[0]=2, nums=[2,2,2,3], write=1
- read=2 (2): keep -> nums[1]=2, nums=[2,2,2,3], write=2
- read=3 (3): skip, write=2 => k=2, prefix [2,2]

Pitfalls to avoid

• Returning a new slice instead of the new length.
• Advancing write when you skip a value.
• Forgetting that nums may be empty.

Debugging lens

Test mixed survivor values, not only repeated survivors: [3,1,3,2] must produce [1,2]. Assert k before slicing nums[:k], and do not compare the unspecified tail.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• The caller will inspect nums[:k] only; values beyond k are irrelevant.

Reconstruction checkpoint

For nums=[3,1,3,2,1] and val=3, what length and valid prefix must be returned?

Return to Array & String · Module quiz