Why it works
- The array is sorted, so equal numbers stand next to each other. A repeat can only follow its own number, so comparing with the last number written is enough: no need to look further back.
- Left of write lies each number met so far, once and in ascending order. A new number is larger than all of them, so it goes right after them, at nums[write].
- When a number is written, write is never to the right of read, so a write only covers a cell that has already been read. No number still to be read is lost.
Complexity
Time O(n): read passes the array once, and each step does one comparison and at most one write. Memory O(1): two indices, and the numbers are rewritten inside the same array.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗