Remove Element

01 · Question

Given nums and val, remove every val in-place and return the new length k. Only the first k positions matter after the operation.

02 · Analysis

Use a read pointer i and a write pointer k:

i scans every value.
If nums[i] != val, write it to nums[k] and advance k.
The invariant is: nums[0:k] contains exactly the values we are keeping.

The point: treat the input array as the output buffer and compact the kept values into its front.

Complexity: $O(n)$ time and $O(1)$ extra space.

03 · Solution

Write each kept value forward

1def removeElement(nums: List[int], val: int) -> int:
2    k = 0
3    for i in range(len(nums)):
4        if nums[i] != val:
5            nums[k] = nums[i]
6            k += 1
7    return k

Design Dynamic Array

Concatenation of Array