First Unique Number Stream

First Unique Number Stream

Hard Python Dictionaries 10 views
Explanation Complexity

Problem Statement

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.

Example

8
ADD 5
ADD 3
FIRST
ADD 5
FIRST
ADD 3
ADD 7
FIRST
5
3
7

Constraints

1

Input / Output Format

Input Format
First line q. Next q lines operations.
Output Format
Outputs for FIRST.
Constraints
1

Examples

Input:
8 ADD 5 ADD 3 FIRST ADD 5 FIRST ADD 3 ADD 7 FIRST
Output:
5 3 7

Example Solution (Public)

Python 
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))

Official Solution Code

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))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.