622. Removing Every Copy of a Value
Given n integers and a value v, remove every occurrence of v. The values that remain keep
their original relative ORDER.
Print how many values remain, and then those values.
3 2 2 3, remove 3 -> 2
2 2
0 1 2 2 3 0 4 2, remove 2 -> 5
0 1 3 0 4
2 2 2, remove 2 -> 0
## Two pointers moving the same way
One pointer READS and one WRITES, and they move at different speeds:
w = 0
for r in 0 .. n-1:
if a[r] != v:
a[w] = a[r]
w += 1
answer: w, and a[0..w-1]
r advances every step; w only when something is kept. So w <= r always, which is what
makes writing into the same array safe: the cell being written has already been read.
That invariant is the whole idea, and it is worth stating out loud before writing the loop. Compacting in place without it is where the bugs live.
## Why not shift on every removal
Removing an element by shifting everything after it back by one is O(n) per removal, so
O(n^2) in total when most values match. The read and write pointers do it in one pass by
never moving anything twice.
## What happens after the write pointer
The cells from w to n-1 still hold old values. They are not cleared and they are not part
of the answer; the count w is what says where the answer stops.
That is why the output prints the count FIRST. A solution that prints the whole array, or that pads the tail with zeros, is answering a different question.
## Boundaries
If every value matches, the answer is 0 and nothing follows it on a second line.
If nothing matches, everything survives in its original order.
## Cost
Time O(n). Space O(1) beyond the input.
Constraints - `0 ≤ n ≤ 200000` - `-10^9 ≤ each value and v ≤ 10^9`
Input
The first line contains two integers n and v.
The second line contains n integers. It is absent when n is 0.
Output
Print the number of remaining values on the first line. If that number is not zero, print those values on a second line, in their original order, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.