Why it works
- 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.
- 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.
- 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 ↗