Remove in place
Drop every copy of a value by keeping the rest at the front. About 8 minutes.
Removing is really keeping
Deleting a value from the middle of an array makes every later value shuffle one box left. Do that for every copy and you're shuffling again and again, which gets slow on a long list.
Turn it around: instead of removing what you don't want, keep what you do want, at the front, with the same reader and writer as before. The writer only moves for values you keep.
Read 2: that's val, skip it.
The answer is the front part
When the reader finishes, the first few boxes, up to the writer, hold exactly the values you kept, in order. The rest of the array is leftover junk from before.
So return only the front part, up to the writer. Returning the whole array would hand back those leftovers too, which looks right at a glance and is wrong.
write = 0
for x in nums:
if x != val:
nums[write] = x
write += 1
return nums[:write]After keeping the non-5 values of 5, 3, 5, 6 at the front, what does the whole array look like, before you cut it?
- A3, 6, 5, 6 (keep the first 2)
- B3, 6
- C3, 6, 0, 0
Show the answer
3, 6, 5, 6 (keep the first 2). 3 and 6 were copied to the front. The last two boxes are leftovers.
Remove a value
You get a list and a value, val. Remove every copy of val, keeping the other values in their original order, by compacting them to the front of the same list. Return the list of kept values.
nums = [2, 7, 2, 1, 8], val = 2 → [7, 1, 8]
0 ≤ n ≤ 1,000,000