Remove every zero from an int slice in place, returning the trimmed slice
Implement remove(in) that deletes every 0 from the slice and returns the result. Do it in place, without allocating a second slice. Requirement: O(n) time, O(1) extra space. Examples: remove([]) → []; remove([0]) → []; remove([1,0,0,2]) → [1,2].
func remove(in []int) []int {
// your code here
return nil
}Write the implementation.
Use a write index j starting at 0. Scan with a read index i; whenever in[i] != 0, copy it to in[j] and advance j. After the pass, the first j elements are the non-zeros, so return in[:j]. This compacts in place with one pass — O(n) time and O(1) extra space — and works for the empty and all-zero cases.
- ✗Splicing with
appendper zero, which is O(n²) not O(n) - ✗Allocating a new slice and calling that in place
- ✗Forgetting to return
in[:j]and returning the full slice
- →How would you also zero out the trailing elements to release references?
- →How does this two-pointer compaction generalize to removing by a predicate?
Solution
Two pointers in one slice: i reads, j writes. Copy only the non-zeros.
func remove(in []int) []int {
j := 0
for i := 0; i < len(in); i++ {
if in[i] != 0 {
in[j] = in[i]
j++
}
}
return in[:j]
}
// remove([]int{1, 0, 0, 2}) -> [1 2]Each non-zero element shifts left into its final position. After the pass the first j elements are the result, and in[:j] trims the tail. One pass is O(n) time; no new slice is allocated, so O(1) extra space.
⚠️ A common mistake is splicing zeros out with append(in[:i], in[i+1:]...) in a loop: that is O(n²) because each splice shifts the tail.
