First Unique Character in a Stream

🎯

First Unique Character in a Stream

mediumSTACKAmazonBloomberg

Imagine you're monitoring a live chat stream and want to instantly identify the first unique character typed so far at any moment.

💡 This problem tests your ability to maintain order and frequency information simultaneously. Beginners often struggle because they try to scan the entire stream repeatedly instead of efficiently tracking uniqueness as new characters arrive.

📋

Problem Statement

Given a stream of characters arriving one by one, design a data structure that supports two operations: (1) add a character to the stream, and (2) return the first unique character in the stream so far. If no unique character exists, return '#'.

1 ≤ number of characters in the stream ≤ 10^5Characters are lowercase English letters ('a' to 'z')

💡

Example

Input"Stream: a, b, c, a, c, b, d"

Outputa, a, a, b, b, #, d

After each character is added, the first unique character is updated. Initially 'a' is unique, after adding 'b' and 'c' 'a' remains unique. When 'a' repeats, 'b' becomes first unique, and so forth.

• Stream with all repeating characters → always returns '#'
• Stream with only one character → returns that character
• Stream where unique character appears late → returns '#' until unique appears
• Stream with continuous unique characters → returns the first character added

⚠️

Common Mistakes

Not removing repeated characters from the queue front

Incorrect first unique character returned after duplicates appear

✅ Always dequeue characters from the front whose frequency is more than 1

Using a frequency map but scanning entire stream each time

Solution becomes inefficient and may time out

✅ Use a queue to track candidates and avoid full scans

Not handling empty queue case when no unique character exists

Code may crash or return wrong output

✅ Return '#' when queue is empty

Using a map for frequency when input is limited to lowercase letters

Slightly slower and more memory usage

✅ Use fixed-size frequency array indexed by character

🧠

Brute Force (Scan Entire Stream Each Time)

💡 This approach is the most straightforward and helps understand the problem deeply by simulating the process without optimization.

Intuition

For each new character added, scan the entire stream from the start to find the first character that appears exactly once.

Algorithm

1. Maintain a list of all characters seen so far.
2. For each new character, append it to the list.
3. Scan the list from the beginning to find the first character with frequency 1.
4. Return that character or '#' if none found.

💡 The challenge is realizing that scanning the entire list every time is costly but conceptually simple.

</>

Code

from collections import Counter

def first_unique_stream(stream):
    result = []
    chars = []
    for ch in stream:
        chars.append(ch)
        freq = Counter(chars)
        first_unique = '#'
        for c in chars:
            if freq[c] == 1:
                first_unique = c
                break
        result.append(first_unique)
    return result

# Driver code
if __name__ == '__main__':
    stream = ['a', 'b', 'c', 'a', 'c', 'b', 'd']
    print(first_unique_stream(stream))  # Expected: ['a', 'a', 'a', 'b', 'b', '#', 'd']

Line Notes

from collections import CounterImport Counter to count frequencies easily

chars.append(ch)Add the new character to the list to keep full stream

freq = Counter(chars)Count frequencies of all characters seen so far

for c in chars:Scan from start to find first unique character

import java.util.*;

public class FirstUniqueStream {
    public static List<Character> firstUniqueStream(char[] stream) {
        List<Character> result = new ArrayList<>();
        List<Character> chars = new ArrayList<>();
        for (char ch : stream) {
            chars.add(ch);
            Map<Character, Integer> freq = new HashMap<>();
            for (char c : chars) {
                freq.put(c, freq.getOrDefault(c, 0) + 1);
            }
            char firstUnique = '#';
            for (char c : chars) {
                if (freq.get(c) == 1) {
                    firstUnique = c;
                    break;
                }
            }
            result.add(firstUnique);
        }
        return result;
    }

    public static void main(String[] args) {
        char[] stream = {'a', 'b', 'c', 'a', 'c', 'b', 'd'};
        System.out.println(firstUniqueStream(stream)); // Expected: [a, a, a, b, b, #, d]
    }
}

Line Notes

List<Character> chars = new ArrayList<>();Store all characters seen so far

Map<Character, Integer> freq = new HashMap<>();Frequency map for current stream

for (char c : chars)Find first unique character by scanning from start

char firstUnique = '#';Initialize first unique character as '#' indicating none found yet

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<char> firstUniqueStream(const vector<char>& stream) {
    vector<char> result;
    vector<char> chars;
    for (char ch : stream) {
        chars.push_back(ch);
        unordered_map<char, int> freq;
        for (char c : chars) {
            freq[c]++;
        }
        char firstUnique = '#';
        for (char c : chars) {
            if (freq[c] == 1) {
                firstUnique = c;
                break;
            }
        }
        result.push_back(firstUnique);
    }
    return result;
}

int main() {
    vector<char> stream = {'a', 'b', 'c', 'a', 'c', 'b', 'd'};
    vector<char> res = firstUniqueStream(stream);
    for (char c : res) cout << c << ' ';
    cout << endl; // Expected: a a a b b # d
    return 0;
}

Line Notes

vector<char> chars;Keep track of all characters seen so far

unordered_map<char, int> freq;Frequency map for current characters

for (char c : chars)Find first unique character by scanning from start

char firstUnique = '#';Initialize first unique character as '#' indicating none found yet

function firstUniqueStream(stream) {
    const result = [];
    const chars = [];
    for (const ch of stream) {
        chars.push(ch);
        const freq = {};
        for (const c of chars) {
            freq[c] = (freq[c] || 0) + 1;
        }
        let firstUnique = '#';
        for (const c of chars) {
            if (freq[c] === 1) {
                firstUnique = c;
                break;
            }
        }
        result.push(firstUnique);
    }
    return result;
}

// Driver code
const stream = ['a', 'b', 'c', 'a', 'c', 'b', 'd'];
console.log(firstUniqueStream(stream)); // Expected: ['a', 'a', 'a', 'b', 'b', '#', 'd']

Line Notes

const chars = [];Store all characters seen so far

const freq = {};Frequency map for current stream

for (const c of chars)Find first unique character by scanning from start

let firstUnique = '#';Initialize first unique character as '#' indicating none found yet

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each of the n characters, we scan up to n characters to find the first unique, resulting in O(n^2) time. Space is O(n) to store the stream.

💡 For n=1000, this means about 1,000,000 operations, which is inefficient for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is essential to understand the problem before optimizing.

🧠

Using Frequency Map + Queue

💡 This approach improves efficiency by tracking frequencies and maintaining a queue of candidates for first unique character.

Intuition

Keep a frequency map to count occurrences and a queue to store characters that might be unique. Remove characters from the queue front if they are no longer unique.

Algorithm

1. Initialize a frequency map and an empty queue.
2. For each incoming character, increment its frequency.
3. Add the character to the queue if it's the first time seen.
4. While the queue front character frequency is more than 1, dequeue it.
5. The front of the queue is the first unique character; if empty, return '#'.

💡 The key insight is that the queue always holds candidates for first unique, so we only check the front.

</>

Code

from collections import deque

def first_unique_stream(stream):
    freq = {}
    q = deque()
    result = []
    for ch in stream:
        freq[ch] = freq.get(ch, 0) + 1
        if freq[ch] == 1:
            q.append(ch)
        while q and freq[q[0]] > 1:
            q.popleft()
        result.append(q[0] if q else '#')
    return result

# Driver code
if __name__ == '__main__':
    stream = ['a', 'b', 'c', 'a', 'c', 'b', 'd']
    print(first_unique_stream(stream))  # Expected: ['a', 'a', 'a', 'b', 'b', '#', 'd']

Line Notes

freq[ch] = freq.get(ch, 0) + 1Update frequency count for current character

if freq[ch] == 1:Add character to queue only if first occurrence

while q and freq[q[0]] > 1:Remove characters from queue front if repeated

result.append(q[0] if q else '#')Append first unique or '#' if none

import java.util.*;

public class FirstUniqueStream {
    public static List<Character> firstUniqueStream(char[] stream) {
        Map<Character, Integer> freq = new HashMap<>();
        Queue<Character> q = new LinkedList<>();
        List<Character> result = new ArrayList<>();
        for (char ch : stream) {
            freq.put(ch, freq.getOrDefault(ch, 0) + 1);
            if (freq.get(ch) == 1) {
                q.offer(ch);
            }
            while (!q.isEmpty() && freq.get(q.peek()) > 1) {
                q.poll();
            }
            result.add(q.isEmpty() ? '#' : q.peek());
        }
        return result;
    }

    public static void main(String[] args) {
        char[] stream = {'a', 'b', 'c', 'a', 'c', 'b', 'd'};
        System.out.println(firstUniqueStream(stream)); // Expected: [a, a, a, b, b, #, d]
    }
}

Line Notes

freq.put(ch, freq.getOrDefault(ch, 0) + 1);Increment frequency count for character

if (freq.get(ch) == 1)Add character to queue only if first time seen

while (!q.isEmpty() && freq.get(q.peek()) > 1)Remove repeated characters from queue front

result.add(q.isEmpty() ? '#' : q.peek());Add first unique or '#' if none

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<char> firstUniqueStream(const vector<char>& stream) {
    unordered_map<char, int> freq;
    queue<char> q;
    vector<char> result;
    for (char ch : stream) {
        freq[ch]++;
        if (freq[ch] == 1) {
            q.push(ch);
        }
        while (!q.empty() && freq[q.front()] > 1) {
            q.pop();
        }
        result.push_back(q.empty() ? '#' : q.front());
    }
    return result;
}

int main() {
    vector<char> stream = {'a', 'b', 'c', 'a', 'c', 'b', 'd'};
    vector<char> res = firstUniqueStream(stream);
    for (char c : res) cout << c << ' ';
    cout << endl; // Expected: a a a b b # d
    return 0;
}

Line Notes

freq[ch]++;Increment frequency count for character

if (freq[ch] == 1)Add character to queue only if first occurrence

while (!q.empty() && freq[q.front()] > 1)Remove repeated characters from queue front

result.push_back(q.empty() ? '#' : q.front());Append first unique or '#' if none

function firstUniqueStream(stream) {
    const freq = {};
    const q = [];
    const result = [];
    for (const ch of stream) {
        freq[ch] = (freq[ch] || 0) + 1;
        if (freq[ch] === 1) {
            q.push(ch);
        }
        while (q.length && freq[q[0]] > 1) {
            q.shift();
        }
        result.push(q.length ? q[0] : '#');
    }
    return result;
}

// Driver code
const stream = ['a', 'b', 'c', 'a', 'c', 'b', 'd'];
console.log(firstUniqueStream(stream)); // Expected: ['a', 'a', 'a', 'b', 'b', '#', 'd']

Line Notes

freq[ch] = (freq[ch] || 0) + 1;Update frequency count for character

if (freq[ch] === 1)Add character to queue only if first occurrence

while (q.length && freq[q[0]] > 1)Remove repeated characters from queue front

result.push(q.length ? q[0] : '#');Append first unique or '#' if none

⏱

Complexity

TimeO(n)

SpaceO(n)

Each character is enqueued and dequeued at most once, so total operations are linear in n. Frequency map uses O(n) space.

💡 For n=100000, this approach can handle the input efficiently within time limits.

Interview Verdict: Accepted / Optimal for interview coding

This approach balances clarity and efficiency, making it ideal to implement in interviews.

🧠

Optimized Using Fixed-Size Frequency Array + Queue

💡 Since input characters are lowercase letters, we can optimize frequency storage using a fixed-size array instead of a map.

Intuition

Replace the frequency map with an integer array of size 26 indexed by character to speed up frequency updates and checks.

Algorithm

1. Initialize an integer array freq of size 26 to zero and an empty queue.
2. For each character, increment freq at its index.
3. Add character to queue if first occurrence.
4. Remove characters from queue front if freq > 1.
5. Return front of queue or '#' if empty.

💡 This approach is a direct optimization of the previous one by leveraging input constraints.

</>

Code

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26
    q = deque()
    result = []
    for ch in stream:
        idx = ord(ch) - ord('a')
        freq[idx] += 1
        if freq[idx] == 1:
            q.append(ch)
        while q and freq[ord(q[0]) - ord('a')] > 1:
            q.popleft()
        result.append(q[0] if q else '#')
    return result

# Driver code
if __name__ == '__main__':
    stream = ['a', 'b', 'c', 'a', 'c', 'b', 'd']
    print(first_unique_stream(stream))  # Expected: ['a', 'a', 'a', 'b', 'b', '#', 'd']

Line Notes

freq = [0] * 26Initialize fixed-size frequency array for lowercase letters

idx = ord(ch) - ord('a')Map character to index 0-25

freq[idx] += 1Increment frequency count in array

while q and freq[ord(q[0]) - ord('a')] > 1Check frequency using array for queue front

import java.util.*;

public class FirstUniqueStream {
    public static List<Character> firstUniqueStream(char[] stream) {
        int[] freq = new int[26];
        Queue<Character> q = new LinkedList<>();
        List<Character> result = new ArrayList<>();
        for (char ch : stream) {
            int idx = ch - 'a';
            freq[idx]++;
            if (freq[idx] == 1) {
                q.offer(ch);
            }
            while (!q.isEmpty() && freq[q.peek() - 'a'] > 1) {
                q.poll();
            }
            result.add(q.isEmpty() ? '#' : q.peek());
        }
        return result;
    }

    public static void main(String[] args) {
        char[] stream = {'a', 'b', 'c', 'a', 'c', 'b', 'd'};
        System.out.println(firstUniqueStream(stream)); // Expected: [a, a, a, b, b, #, d]
    }
}

Line Notes

int[] freq = new int[26];Fixed-size frequency array for lowercase letters

int idx = ch - 'a';Convert character to array index

freq[idx]++;Increment frequency count

while (!q.isEmpty() && freq[q.peek() - 'a'] > 1)Check frequency using array for queue front

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<char> firstUniqueStream(const vector<char>& stream) {
    vector<int> freq(26, 0);
    queue<char> q;
    vector<char> result;
    for (char ch : stream) {
        int idx = ch - 'a';
        freq[idx]++;
        if (freq[idx] == 1) {
            q.push(ch);
        }
        while (!q.empty() && freq[q.front() - 'a'] > 1) {
            q.pop();
        }
        result.push_back(q.empty() ? '#' : q.front());
    }
    return result;
}

int main() {
    vector<char> stream = {'a', 'b', 'c', 'a', 'c', 'b', 'd'};
    vector<char> res = firstUniqueStream(stream);
    for (char c : res) cout << c << ' ';
    cout << endl; // Expected: a a a b b # d
    return 0;
}

Line Notes

vector<int> freq(26, 0);Fixed-size frequency array for lowercase letters

int idx = ch - 'a';Map character to index 0-25

freq[idx]++;Increment frequency count

while (!q.empty() && freq[q.front() - 'a'] > 1)Check frequency for queue front using array

function firstUniqueStream(stream) {
    const freq = new Array(26).fill(0);
    const q = [];
    const result = [];
    for (const ch of stream) {
        const idx = ch.charCodeAt(0) - 'a'.charCodeAt(0);
        freq[idx]++;
        if (freq[idx] === 1) {
            q.push(ch);
        }
        while (q.length && freq[q[0].charCodeAt(0) - 'a'.charCodeAt(0)] > 1) {
            q.shift();
        }
        result.push(q.length ? q[0] : '#');
    }
    return result;
}

// Driver code
const stream = ['a', 'b', 'c', 'a', 'c', 'b', 'd'];
console.log(firstUniqueStream(stream)); // Expected: ['a', 'a', 'a', 'b', 'b', '#', 'd']

Line Notes

const freq = new Array(26).fill(0);Initialize fixed-size frequency array

const idx = ch.charCodeAt(0) - 'a'.charCodeAt(0);Map character to index 0-25

freq[idx]++;Increment frequency count

while (q.length && freq[q[0].charCodeAt(0) - 'a'.charCodeAt(0)] > 1)Remove repeated characters from queue front

⏱

Complexity

TimeO(n)

SpaceO(1)

Frequency array size is fixed (26), so space is constant. Time remains linear as each character is processed once.

💡 This approach is the fastest and most memory-efficient for lowercase English letters.

Interview Verdict: Accepted / Optimal and space efficient

This is the best practical solution for this problem when input is restricted to lowercase letters.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 or 3 are best to implement in interviews due to their efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Frequency Map + Queue	O(n)	O(n)	No	N/A	Code this for optimal clarity and efficiency
3. Fixed-Size Frequency Array + Queue	O(n)	O(1)	No	N/A	Code this if input constraints allow for best performance

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the inefficiency and propose the queue + frequency map approach.Step 4: Code the optimal solution using a queue and frequency map or array.Step 5: Test with sample inputs and discuss edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Discuss: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to maintain order and frequency efficiently, your understanding of data structures like queues and hash maps, and your coding accuracy.

Common Follow-ups

• What if the stream contains all ASCII characters? → Use a larger frequency array or hash map.
• How to modify for a stream of numbers instead of characters? → Use similar frequency map and queue approach.

💡 Follow-ups test your ability to generalize the solution beyond lowercase letters and adapt data structures accordingly.

🔍

Pattern Recognition

When to Use

1) You need to find the first unique element in a sequence. 2) The sequence is dynamic or streaming. 3) You must maintain order and frequency efficiently. 4) The problem hints at using a queue or ordered structure.

Signature Phrases

first unique characterstream of charactersreturn '#' if none

NOT This Pattern When

Problems that only require frequency counting without order, or problems that require longest substring without repeating characters (sliding window pattern).

Similar Problems

First Unique Character in a String - static version of this problemDesign a Data Structure for First Unique Number - similar queue + frequency approach

Practice

1. Consider the following Python code implementing the two-pass counter approach for longest valid parentheses. What is the final returned value when the input string is "(()"?

def longestValidParentheses(s: str) -> int:
    left = right = max_len = 0
    # Left to right scan
    for ch in s:
        if ch == '(': left += 1
        else: right += 1
        if left == right:
            max_len = max(max_len, 2 * right)
        elif right > left:
            left = right = 0
    left = right = 0
    # Right to left scan
    for ch in reversed(s):
        if ch == ')': right += 1
        else: left += 1
        if left == right:
            max_len = max(max_len, 2 * left)
        elif left > right:
            left = right = 0
    return max_len

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace left to right scan for input "(()"

   Characters: '(', '(', ')' - left=1, right=0 - left=2, right=0 - left=2, right=1 No reset since right < left; max_len updated only when left==right (never here)

2. Step 2: Trace right to left scan

   Characters reversed: ')', '(', '(' - right=1, left=0 - right=1, left=1 -> left==right, max_len = max(0, 2*1) = 2 - right=1, left=2 -> left > right, reset left=right=0 Return max_len = 2

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest valid substring is "()" with length 2 [OK]

Hint: Two-pass scan finds max length 2 for "(()" [OK]

Common Mistakes:

• Confusing max_len update condition
• Forgetting right to left scan resets
• Off-by-one counting

2. Consider the following buggy code snippet for the optimal calculator. Which line contains the subtle bug that causes incorrect results for expressions with negative division?

medium

A. Line with 'current_op = c' updating the operator

B. Line with 'last_num = last_num // current_num' (integer division without handling negatives)

C. Line with 'current_num = current_num * 10 + int(c)' parsing digits

D. Line with 'total += last_num' inside '+' case

Solution

1. Step 1: Identify division handling

   Integer division of negative numbers must truncate toward zero, not floor.

2. Step 2: Locate bug line

   The line 'last_num = last_num // current_num' does not handle negative last_num correctly, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct negative division requires special handling, missing here [OK]

Hint: Negative division truncation requires special code [OK]

Common Mistakes:

• Ignoring negative division truncation
• Forgetting to add last_num at end
• Misparsing digits

3. What is the time complexity of the getMin() operation in the single stack with encoded minimum values approach for the Minimum Stack problem, and why?

medium

A. O(1), because the minimum value is stored and updated during push and pop operations.

B. O(n), because it needs to scan the entire stack to find the minimum.

C. O(log n), because the stack maintains a balanced structure to track minimums.

D. O(n), because the encoded differences require decoding all elements to find the minimum.

Solution

1. Step 1: Understand getMin() operation

   In the encoded stack approach, minVal is updated on every push/pop, so getMin() just returns minVal.

2. Step 2: Analyze complexity

   Since getMin() returns a stored variable without iteration, it runs in O(1) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   getMin() is a direct variable access, no loops [OK]

Hint: getMin() returns stored minVal updated on push/pop [OK]

Common Mistakes:

• Assuming getMin scans stack
• Confusing encoded values require decoding
• Thinking balanced tree needed for min tracking

4. The following code attempts to implement the optimized next greater element algorithm. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line with 'while stack and num > stack[-1]:' condition

B. Line 'while stack:' loop assigning -1 to remaining elements

C. Line 'nums1_set.remove(smaller)' inside the if condition

D. Line missing 'next_greater_map[smaller] = num' inside the while loop

Solution

1. Step 1: Identify missing mapping assignment

   The code pops smaller elements but does not assign their next greater element in next_greater_map, causing missing or incorrect results.

2. Step 2: Confirm other lines are correct

   The while condition, set removal, and final assignment of -1 are all correct and necessary for correctness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without mapping assignment, queries for nums1 elements fail [OK]

Hint: Mapping next greater elements must happen immediately after popping [OK]

Common Mistakes:

• Forgetting to assign next greater element after popping from stack
• Incorrectly removing elements from nums1_set too early
• Misplacing the final assignment of -1 for leftover stack elements

5. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character might be compared multiple times during matching

B. O(n) because each character is processed once with constant-time stack operations

C. O(n log n) due to sorting or ordering operations on the stack

D. O(n) for time but O(n^2) for space due to stack growth in worst case

Solution

1. Step 1: Identify complexity of outer loop

   The algorithm iterates over each character exactly once, so the loop is O(n).

2. Step 2: Check stack operations

   Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant-time stack ops -> O(n) time [OK]

Hint: Each character processed once with O(1) stack ops [OK]

Common Mistakes:

• Confusing with brute force O(n^2) approach