Remove Element

Easy#27same direction

You get an array of numbers and one number, val. Get rid of every copy of val inside the same array, without a second one, and return how many numbers are left. Those numbers must fill the start of the array, in any order; what lies after them does not matter. Our example: [4, 1, 4, 4, 2, 3], val = 4 → 3, and the array starts with [1, 2, 3].

27 Remove ElementWalkthrough · 1×

Example: [4, 1, 4, 4, 2, 3], val = 4. Both pointers walk right: read looks at every number, write marks where the next number we keep goes. Every 4 is skipped.

041124344253write
kept: the answer so farbeing readjust copied hereequals val: skippedalready copied leftnot read yet

write = 0: the first number we keep goes to index 0

01/21
restart · back · play · step
Speed
1function removeElement(nums, val):
2 write = 0
3 for read from 0 to len(nums) - 1:
4 if nums[read] != val:
5 nums[write] = nums[read]
6 write = write + 1
7 return write
state
val
4
write
0
read
–
nums
[4, 1, 4, 4, 2, 3]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Left of write lie exactly the numbers kept so far: each number that is not val is copied to write, and write moves on. So everything left of write is already a finished part of the answer.
  2. write moves at most once per step of read, so it never gets ahead of read. A copy only overwrites a cell read has already looked at: no number is lost before it is checked.
  3. When read reaches the end, every number has been checked once. write is how many are left, and the first write cells hold them.

Complexity

Time O(n): read passes the array once, and each step does at most one copy. Memory O(1): the numbers move inside the same array.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.