First Non-Repeating Character in Stream
A medium Queue problem included in Love Babbar 450. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Queue
- Sheets
- 1
- Core for
- 9 roles
- Platform
- GeeksforGeeks
The problem
Given a stream of integers, return the first non-repeating integer seen so far at each step. If there is no non-repeating integer, return -1.
Example 1
- Input
- stream = [2, 1, 3, 2, 1, 5]
- Output
- [2, 2, 2, 1, 3, 3]
- Why
- After 2: first non-repeating is 2. After 1: still 2. After 3: still 2. After second 2: 2 is repeating, so first non-repeating is 1. After second 1: 1 is also repeating, so first non-repeating is 3. After 5: first non-repeating remains 3.
Example 2
- Input
- stream = [1, 2, 1, 3]
- Output
- [1, 1, 2, 2]
- Why
- After 1 and 2, first non-repeating is 1. After second 1, first non-repeating is 2. After 3, first non-repeating is still 2.
Constraints
- 1 <= stream.length <= 10^5
- 1 <= stream[i] <= 10^5
How to think about it
Updated 2026-09-09The first non-repeating candidate never moves backward in the arrival sequence; it either stays the head of the candidate list or advances forward once repeated. A queue paired with a frequency table tracks arrival order while lazily discarding values from the front the moment their frequency exceeds one.
Approaches, worst first
Frequency map with prefix scan
time O(n^2) · space O(u)
Record counts in a hash table or frequency array. At each step, scan the seen prefix from the beginning until finding the first value with count equal to 1. Repeated scans over dead prefixes degrade to quadratic runtime on long streams.
Queue with lazy evictionWrite this one
time O(n) · space O(u)
Increment frequency on arrival and push the element into a queue. At each step, pop from the queue head while the front element has frequency greater than 1. The head is then the answer, or -1 if the queue is drained. Each unique item is enqueued and dequeued at most once.
Where people lose marks · 3
- Re-adding an element to the queue when seen again, which revives stale copies and re-evaluates invalid candidates later.
- Popping only once instead of using a while loop to discard multiple consecutive duplicates accumulated at the front of the queue.
- Assuming stream values fit in a tiny fixed-size array without checking that values reach 10^5 under the constraints.
The theory behind it
Queue — the ground this problem stands on. All Queue problems
What Queue is
A queue is an orderly checkout line at a grocery store counter where patrons enter at the back and leave from the front. The person who arrives first gets served first, while newcomers wait patiently behind whoever came before them. Unlike a stack which turns back on its latest arrival, a queue preserves fair chronological arrival order, processing tasks strictly from oldest to newest.
When to reach for it
Reach for a queue when exploring states level by level, such as finding the shortest path across an unweighted graph or traversing a tree horizontally. It fits rate-limiting buffers, print spools, asynchronous task schedulers, and sliding cache windows where oldest items expire first. Any problem stating that processing must honor strict time-of-arrival order is an immediate candidate.
How the pattern works
Track two distinct ends: an enqueue boundary at the tail and a dequeue boundary at the head. In breadth traversals, snapshot the queue size before starting an inner loop to process an entire depth tier in one grouped wave. Items currently enqueued represent the frontier of known but unresolved states. Ensure newly generated states are marked visited upon insertion rather than upon extraction to prevent duplicated queue entries.
What each operation costs
| Operation | Time |
|---|---|
| enqueue item at the back | O(1) |
| dequeue item from the front | O(1) |
| inspect the front item | O(1) |
What usually goes wrong with Queue
- Using a standard dynamic array as a queue and removing from index zero, creating hidden linear shifts on every pop operation.
- Marking tree or graph nodes as visited during dequeue instead of enqueue, causing identical nodes to be repeatedly enqueued and blowing up memory consumption.
- Omitting the snapshot of queue size when running level-order sweeps, resulting in parent nodes and newly added child nodes blending into the same loop round.
Which roles need this problem
Queue is a core topic for these 9 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 6 more roles, including Frontend Engineer, Data Engineer, Game Developer.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Queue problems
Problem set and role mapping as of .