First Unique Number Stream
Python
Hard
2 views
Problem Description
You will receive q operations: ADD x or FIRST. ADD adds number x to stream. FIRST should output the first number that has appeared exactly once so far, or -1 if none.
Input Format
First line q. Next q lines operations.
Output Format
Outputs for FIRST.
Sample Test Case
Input:
8
ADD 5
ADD 3
FIRST
ADD 5
FIRST
ADD 3
ADD 7
FIRST
Official Solution
import sys
from collections import deque
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
q=int(lines[0].strip())
count={}
qv=deque()
out=[]
for i in range(1,1+q):
parts=(lines[i] if i<len(lines) else '').split()
if not parts: continue
if parts[0]=='ADD':
x=int(parts[1])
count[x]=count.get(x,0)+1
qv.append(x)
else:
while qv and count.get(qv[0],0)!=1:
qv.popleft()
out.append(str(qv[0] if qv else -1))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!