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.

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

• Invariant: all indices < write are kept values in the correct (original) order.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

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.

Complexity

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

Implementation notes (Go)

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