First unique id in a stream

Scenario

A payments app receives transaction ids one at a time. An id should arrive once, and an id that arrives again points to a retry or a fault.

Support asks for the earliest id that has arrived exactly once so far, at any moment. The stream is long, so each add and each question must take constant time on average.

Your task

Write run_stream(commands, ids).

commands[i] is "add" or "first". For "add", ids[i] is a transaction id. For "first", ids[i] is 0 and is ignored.
"add" records that the id arrived once more.
"first" asks for the id that arrived earliest among the ids that have arrived exactly once so far. It answers -1 when no id has arrived exactly once.
An id that has arrived two or more times is never unique again.
Return one number for each "first", in order.

Examples

Example 1 (traced)#

text2 lines

Input:  commands = ["add", "add", "first", "add", "first", "add", "first", "first"], ids = [5, 7, 0, 5, 0, 7, 0, 0]
Output: [5, 7, -1, -1]

The trace keeps a count for each id and a queue of ids in arrival order.

Step	Command	Counts	Queue (front first)	Answer
1	add 5	5: 1	5
2	add 7	5: 1, 7: 1	5, 7
3	first	same	5, 7	5
4	add 5	5: 2, 7: 1	5, 7
5	first	same	7, because 5 repeated and is dropped	7
6	add 7	5: 2, 7: 2	7
7	first	same	empty, because 7 repeated and is dropped	-1
8	first	same	empty	-1

Example 2#

text2 lines

Input:  commands = ["first"], ids = [0]
Output: [-1]

Nothing has arrived.

Example 3#

text2 lines

Input:  commands = ["add", "first", "add", "first", "add", "first"], ids = [3, 0, 4, 0, 3, 0]
Output: [3, 3, 4]

The id 3 arrives again at the fifth command, so the earliest unique id becomes 4.

Constraints

1 ≤ commands.length = ids.length ≤ 100,000
0 ≤ ids[i] ≤ 1,000,000,000

What does n ≤ 100,000 tell you?

A table of counts makes each add one step. A question that then scans the ids from the oldest walks past every id that has repeated. If 25,000 ids arrive twice before the first unique one, and 45,000 questions follow, that is about 10^9 steps.

You need the count of each id, kept up to date, and the order of arrival, kept so that no question walks past the same repeated id twice.

Scenario

A payments app receives transaction ids one at a time. An id should arrive once, and an id that arrives again points to a retry or a fault.

Support asks for the earliest id that has arrived exactly once so far, at any moment. The stream is long, so each add and each question must take constant time on average.

Your task

Write run_stream(commands, ids).

commands[i] is "add" or "first". For "add", ids[i] is a transaction id. For "first", ids[i] is 0 and is ignored.
"add" records that the id arrived once more.
"first" asks for the id that arrived earliest among the ids that have arrived exactly once so far. It answers -1 when no id has arrived exactly once.
An id that has arrived two or more times is never unique again.
Return one number for each "first", in order.

Examples

Example 1 (traced)#

text2 lines

Input:  commands = ["add", "add", "first", "add", "first", "add", "first", "first"], ids = [5, 7, 0, 5, 0, 7, 0, 0]
Output: [5, 7, -1, -1]

The trace keeps a count for each id and a queue of ids in arrival order.

Step	Command	Counts	Queue (front first)	Answer
1	add 5	5: 1	5
2	add 7	5: 1, 7: 1	5, 7
3	first	same	5, 7	5
4	add 5	5: 2, 7: 1	5, 7
5	first	same	7, because 5 repeated and is dropped	7
6	add 7	5: 2, 7: 2	7
7	first	same	empty, because 7 repeated and is dropped	-1
8	first	same	empty	-1

Example 2#

text2 lines

Input:  commands = ["first"], ids = [0]
Output: [-1]

Nothing has arrived.

Example 3#

text2 lines

Input:  commands = ["add", "first", "add", "first", "add", "first"], ids = [3, 0, 4, 0, 3, 0]
Output: [3, 3, 4]

The id 3 arrives again at the fifth command, so the earliest unique id becomes 4.

Constraints

1 ≤ commands.length = ids.length ≤ 100,000
0 ≤ ids[i] ≤ 1,000,000,000

What does n ≤ 100,000 tell you?

You need the count of each id, kept up to date, and the order of arrival, kept so that no question walks past the same repeated id twice.