DSA Tracker

Visualize

First Non-Repeating Character in a Stream

The queue keeps candidates in arrival order, so the answer is always the front

time O(n) total — each character is pushed once and popped at most oncespace O(k) for the queue and the counts, k = alphabet size

Re-scanning everything seen so far after each character is the obvious answer and it is quadratic. The insight is that 'first' means oldest, and a queue already stores things oldest-first — so the answer is never searched for, it is just the front. A character joins the back when it arrives; once its count passes one it is dead, but deleting it from the middle would cost a scan, so it is left in place and simply thrown away if it ever reaches the front. Every character is therefore pushed once and popped at most once, and each answer is a single peek.

Details

Animated on: stream = "aabcbd" — after every character, report the first character so far that has appeared exactly once, or '#' if there is none. The row drawn is the QUEUE of surviving candidates, not the stream.

Problem:Stream First Non-repeatingMedium

The queue keeps candidates in arrival order, so the answer is always the front

step 1 / 13

a
[0]

'a' arrives and is brand new, so it joins the BACK of the queue as the newest candidate. The queue is now [a] — every character still in the running, in the order it showed up, which is exactly the order the answer has to be picked in.

  • front=0· arr[0] = a
  • back=0· arr[0] = a
Pseudocode
1FUNCTION firstNonRepeating(stream)
2  queue <- empty queue
3  count <- empty map
4  FOR EACH ch IN stream
5    count[ch] <- count[ch] + 1
6    ENQUEUE ch INTO queue
7    WHILE queue IS NOT EMPTY AND count[FRONT(queue)] > 1
8      DEQUEUE FROM queue
9    IF queue IS EMPTY
10      OUTPUT '#'
11    ELSE
12      OUTPUT FRONT(queue)

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. 'a' arrives and is brand new, so it joins the BACK of the queue as the newest candidate. The queue is now [a] — every character still in the running, in the order it showed up, which is exactly the order the answer has to be picked in.
  2. The front 'a' has been seen exactly once, so the drop loop does not run at all — no scan, no search. Queue: [a]. The front 'a' is the oldest character still seen exactly once, so after "a" the answer is 'a'. Output so far: "a".
  3. 'a' arrives for the second time, so it can never be the answer again — and neither can the copy already sitting at index 0. Both are marked dead, but NOT removed: hunting through the queue to delete them would cost a scan every character. They are dropped only when they reach the front.
  4. The front is stale, so drop it: 'a' (seen 2 times), then 'a' (seen 2 times). That emptied the queue: every character in "aa" has repeated, so there is no non-repeating one and the answer is '#'. Output so far: "a#".
  5. 'b' arrives and is brand new, so it joins the BACK of the queue as the newest candidate. The queue is now [b] — every character still in the running, in the order it showed up, which is exactly the order the answer has to be picked in.
  6. The front 'b' has been seen exactly once, so the drop loop does not run at all — no scan, no search. Queue: [b]. The front 'b' is the oldest character still seen exactly once, so after "aab" the answer is 'b'. Output so far: "a#b".
  7. 'c' arrives and is brand new, so it joins the BACK of the queue as the newest candidate. The queue is now [b, c] — every character still in the running, in the order it showed up, which is exactly the order the answer has to be picked in.
  8. The front 'b' has been seen exactly once, so the drop loop does not run at all — no scan, no search. Queue: [b, c]. The front 'b' is the oldest character still seen exactly once, so after "aabc" the answer is 'b'. Output so far: "a#bb".
  9. 'b' arrives for the second time, so it can never be the answer again — and neither can the copy already sitting at index 0. Both are marked dead, but NOT removed: hunting through the queue to delete them would cost a scan every character. They are dropped only when they reach the front.
  10. The front is stale, so drop it: 'b' (seen 2 times). Queue: [c, b]. The front 'c' is the oldest character still seen exactly once, so after "aabcb" the answer is 'c'. Output so far: "a#bbc".
  11. 'd' arrives and is brand new, so it joins the BACK of the queue as the newest candidate. The queue is now [c, b, d] — every character still in the running, in the order it showed up, which is exactly the order the answer has to be picked in.
  12. The front 'c' has been seen exactly once, so the drop loop does not run at all — no scan, no search. Queue: [c, b, d]. The front 'c' is the oldest character still seen exactly once, so after "aabcbd" the answer is 'c'. Output so far: "a#bbcc".
  13. Stream "aabcbd" fully consumed, answers "a#bbcc". Each character was pushed once and popped at most once, so all 6 answers cost O(6) work in total — the queue never had to be searched, only its front read.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Stream First Non-repeating in the editorAll Queue problemsBack to roadmap