Compress repeated scans

Scenario

A Kestrel Freight conveyor scanner reads the code of every parcel that passes and sends the stream of codes to the hub's sorting system. When the belt stalls, the scanner reads the same parcel again and again, so the stream fills with runs of one code.

To save bandwidth, the scanner compresses each run before sending. It writes the code, then the run's length as a negative number if the run is longer than one. Codes are always positive, so the sign marks a length. The scanner's controller has little memory, so it compresses the stream in place.

Your task

Write compress_runs(scans).

scans[i] is the code read at position i of the stream, in order. Every code is positive.
A run is a longest stretch of consecutive scans with the same code. The same code can appear again later as a separate run.
Replace each run by its code. If the run is longer than one scan, follow the code with its length as a negative number. A run of one scan is the code alone, with no -1.
Return the compressed stream as a list.
Edit scans in place with O(1) extra memory, then return the kept prefix. The judge checks only the list you return.

Examples

Example 1 (traced)#

text2 lines

Input:  scans = [7, 7, 7, 3, 9, 9]
Output: [7, -3, 3, 9, -2]

Run starts at	Code	Length	read after the run	Values written	write after	Kept prefix
0	7	3	3	7, -3	2	7, -3
3	3	1	4	3	3	7, -3, 3
4	9	2	6	9, -2	5	7, -3, 3, 9, -2

The run of three 7s becomes 7, -3, and the single 3 stays as it is. After the pass the array holds [7, -3, 3, 9, -2, 9], and the first 5 positions are the answer.

Example 2#

text2 lines

Input:  scans = [4, 8, 4]
Output: [4, 8, 4]

Code 4 appears twice, but not in a row, so there are three runs of one scan each.

Example 3#

text2 lines

Input:  scans = [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
Output: [6, -12]

One run of 12 scans. The length is one value, however many digits it has.

Constraints

1 ≤ scans.length ≤ 10^5
1 ≤ scans[i] ≤ 10^9

What does n ≤ 10^5 tell you?

Building the answer in a second list with no spare room copies the whole answer for every value you add. With no runs at all, that is n × (n − 1) / 2 copies: about 5 × 10^9 at n = 10^5. Aim for O(n).

The compressed stream is never longer than the input. A run of one scan writes one value, and a longer run writes two. So the answer fits in the same array, written from the front.

Scenario

Your task

Write compress_runs(scans).

scans[i] is the code read at position i of the stream, in order. Every code is positive.
A run is a longest stretch of consecutive scans with the same code. The same code can appear again later as a separate run.
Replace each run by its code. If the run is longer than one scan, follow the code with its length as a negative number. A run of one scan is the code alone, with no -1.
Return the compressed stream as a list.
Edit scans in place with O(1) extra memory, then return the kept prefix. The judge checks only the list you return.

Examples

Example 1 (traced)#

text2 lines

Input:  scans = [7, 7, 7, 3, 9, 9]
Output: [7, -3, 3, 9, -2]

Run starts at	Code	Length	read after the run	Values written	write after	Kept prefix
0	7	3	3	7, -3	2	7, -3
3	3	1	4	3	3	7, -3, 3
4	9	2	6	9, -2	5	7, -3, 3, 9, -2

The run of three 7s becomes 7, -3, and the single 3 stays as it is. After the pass the array holds [7, -3, 3, 9, -2, 9], and the first 5 positions are the answer.

Example 2#

text2 lines

Input:  scans = [4, 8, 4]
Output: [4, 8, 4]

Code 4 appears twice, but not in a row, so there are three runs of one scan each.

Example 3#

text2 lines

Input:  scans = [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
Output: [6, -12]

One run of 12 scans. The length is one value, however many digits it has.

Constraints

1 ≤ scans.length ≤ 10^5
1 ≤ scans[i] ≤ 10^9

What does n ≤ 10^5 tell you?

The compressed stream is never longer than the input. A run of one scan writes one value, and a longer run writes two. So the answer fits in the same array, written from the front.