First Unique Character in a Stream

📋

Problem

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

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

Edge cases: Stream with all repeating characters → always returns '#'Stream with only one character → returns that characterStream where unique character appears late → returns '#' until unique appears

</>

IDE

def first_unique_stream(stream: list) -> list:public List<Character> firstUniqueStream(List<Character> stream)vector<char> firstUniqueStream(vector<char> &stream)function firstUniqueStream(stream)

def first_unique_stream(stream):
    # Write your solution here
    pass

class Solution {
    public List<Character> firstUniqueStream(List<Character> stream) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<char> firstUniqueStream(vector<char> &stream) {
    // Write your solution here
    return {};
}

function firstUniqueStream(stream) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ####Always returning '#' regardless of input, ignoring unique characters.✅ Implement frequency counting and queue to track unique characters properly.

Wrong: abcacbdReturning last inserted character instead of first unique.✅ Use a queue to track order of unique characters and update after frequency changes.

Wrong: aaaaaaaNever removing characters from queue when frequency > 1, so first unique never updates.✅ Remove characters from queue front when their frequency exceeds one.

Wrong: aaaa###Off-by-one error in frequency update causing premature '#' output.✅ Update frequency before checking queue and outputting first unique.

Wrong: TLE due to scanning entire stream after each insertion (O(n^2)).✅ Use a queue and frequency map to achieve O(n) time complexity.

✓

Test Cases

Try testing your code with empty and single-character streams to catch base case bugs.

Consider tricky cases where characters repeat in pairs or unique characters appear late.

Optimize your solution to run in linear time using a queue and frequency map.

t1_01basic

Input{"stream":["a","b","c","a","c","b","d"]}

Expected["a","a","a","b","b","#","d"]

⏱ Performance - must finish in 2000ms

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.

💡 Think about tracking character frequencies and their order of arrival.

💡 Use a queue to keep track of candidates for first unique and a frequency map to know counts.

💡 Remove characters from the queue front if their frequency becomes more than one.

Why it failed: Output incorrect because the first unique character was not updated correctly after repeats. Fix by maintaining a queue of unique candidates and updating frequencies properly.

✓ Correctly tracks first unique character after each insertion.

t1_02basic

Input{"stream":["x","y","x","z","y","a"]}

Expected["x","x","y","y","#","a"]

⏱ Performance - must finish in 2000ms

Stream adds 'x', 'y', then 'x' repeats so 'y' is first unique, then 'z' added and 'y' still unique, 'y' repeats so no unique character remains, finally 'a' added which becomes first unique.

💡 Track frequencies and order of characters as they arrive.

💡 When a character frequency exceeds one, remove it from the queue of unique candidates.

💡 The first unique is always at the front of the queue after removals.

Why it failed: Fails to update first unique when characters repeat and are removed from the queue. Fix by dequeuing non-unique characters until front is unique or queue is empty.

✓ Properly updates first unique character after each stream addition.

t2_01edge

Input{"stream":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty stream means no characters, so output is empty list.

💡 Consider what happens when no characters are added.

💡 Your code should handle empty input gracefully without errors.

💡 Return an empty list immediately if stream is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a check for empty stream and returning empty list.

✓ Handles empty input correctly by returning empty output.

t2_02edge

Input{"stream":["z"]}

Expected["z"]

⏱ Performance - must finish in 2000ms

Single character stream means that character is unique and output is that character.

💡 Check behavior when stream length is one.

💡 Frequency of the single character is one, so it is unique.

💡 Output should be the single character itself.

Why it failed: Fails to return the single character as unique, possibly returning '#' or empty. Fix by ensuring single character frequency is counted correctly.

✓ Correctly returns the single character as first unique.

t2_03edge

Input{"stream":["a","a","a","a"]}

Expected["a","#","#","#"]

⏱ Performance - must finish in 2000ms

All characters are the same and repeated, so after first insertion 'a' is unique, then repeats cause no unique characters, output '#'.

💡 Track frequency carefully for repeated characters.

💡 When frequency > 1, character is no longer unique and should not be output.

💡 Output '#' when no unique character exists.

Why it failed: Fails to output '#' after repeats, possibly returning repeated character incorrectly. Fix by checking frequency > 1 and outputting '#' accordingly.

✓ Correctly outputs '#' when no unique character remains.

t3_01corner

Input{"stream":["a","b","c","d","e","f","g"]}

Expected["a","a","a","a","a","a","a"]

⏱ Performance - must finish in 2000ms

All characters are unique and distinct, so first unique remains the first character 'a' throughout.

💡 Check if your code incorrectly removes unique characters prematurely.

💡 Ensure queue only removes characters when frequency > 1.

💡 Maintain order of insertion to keep first unique stable.

Why it failed: Fails by removing unique characters too early or returning wrong first unique. Fix by only removing characters from queue when frequency > 1.

✓ Maintains first unique correctly when all characters are unique.

t3_02corner

Input{"stream":["a","a","b","b","c","c","d"]}

Expected["a","#","b","#","c","#","d"]

⏱ Performance - must finish in 2000ms

Characters repeat in pairs, so first unique changes accordingly, output '#' when no unique character exists.

💡 Watch for off-by-one errors in frequency updates.

💡 Ensure characters are removed from queue only after frequency increments.

💡 Check that first unique updates correctly after each insertion.

Why it failed: Fails to update first unique correctly after pairs repeat, possibly off-by-one frequency bug. Fix by updating frequency before checking queue.

✓ Correctly updates first unique after each character insertion.

t3_03corner

Input{"stream":["a","b","a","b","c","c","d"]}

Expected["a","a","b","b","c","#","d"]

⏱ Performance - must finish in 2000ms

Characters 'a' and 'b' repeat causing no unique until 'd' appears at end.

💡 Beware of greedy approaches that pick first unique without updating frequencies.

💡 Use a queue and frequency map to track unique candidates properly.

💡 Remove characters from queue front when frequency > 1 before output.

Why it failed: Greedy approach fails by not updating queue after repeats, returning stale first unique. Fix by dequeuing non-unique characters before output.

✓ Correctly handles updates to first unique with repeated characters.

t4_01performance

Input{"stream":["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v"]}

Expectednull

⏱ Performance - must finish in 2000ms

Stream length n=100, solution must run in O(n) time to complete within 2 seconds.

💡 Brute force scanning each time is O(n^2) and will TLE.

💡 Use frequency map and queue to achieve O(n) time complexity.

💡 Avoid rescanning entire stream after each insertion.

Why it failed: TLE due to O(n^2) brute force approach scanning entire stream each insertion. Fix by using queue + frequency map for O(n) solution.

✓ Solution runs in O(n) time confirming efficient approach.

Practice

1. Given the following Python code implementing the optimal stack-less calculator, what is the final returned value when the input string is "3+2*2"?

easy

A. 5

B. 10

C. 8

D. 7

Solution

1. Step 1: Trace first number and operator

   Read '3', current_op='+', total=0, last_num=0. On '+', total += last_num (0), last_num=3.

2. Step 2: Process '2*2'

   Read '2', operator '*', current_op='+', so total += last_num (3), last_num=2. Then read '2' after '*', current_op='*', last_num=2*2=4.

3. Step 3: End of string

   Add last_num (4) to total (3), total=7.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   3 + (2*2) = 7 matches traced total [OK]

Hint: Multiplication evaluated before addition, total accumulates last_num [OK]

Common Mistakes:

• Adding numbers before multiplication
• Off-by-one in loop end
• Not adding last_num at end

2. Given the following Python code for the Basic Calculator, what is the value of result immediately after processing the character ')' at index 6 in the input string "(1+(2-3))"?

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1
    num = 0
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':  # Push current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':  # Add last number and combine
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
    result += sign * num
    return result

easy

A. 0

B. 0

C. 0

D. 0

Solution

1. Step 1: Trace characters up to index 6

   Input: "(1+(2-3))" - i=0:'(' push 0 and 1, result=0, sign=1 - i=1:'1' num=1 - i=2:'+' result=0+1*1=1, num=0, sign=1 - i=3:'(' push 1 and 1, result=0, sign=1 - i=4:'2' num=2 - i=5:'-' result=0+1*2=2, num=0, sign=-1 - i=6:'3' num=3

2. Step 2: Process character at index 6 (')')

   At ')': result += sign*num = 2 + (-1)*3 = -1 num=0 result *= stack.pop() -> result *= 1 -> -1 result += stack.pop() -> -1 + 1 = 0

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Result after popping stack is 0 [OK]

Hint: Remember to apply sign*num before popping stack [OK]

Common Mistakes:

• Forgetting to add last number before popping stack

3. You are given a string containing encoded patterns like 3[a2[c]], where numbers indicate how many times the substring inside brackets should be repeated. Which algorithmic approach guarantees an optimal and correct decoding of such nested patterns?

easy

A. Greedy approach that expands the first encountered bracketed substring repeatedly until no brackets remain

B. Simple recursion that decodes substrings without using any auxiliary data structures

C. Dynamic programming approach that builds solutions bottom-up using substring indices

D. Stack-based iterative approach that uses two stacks to track counts and substrings, handling nested patterns correctly

Solution

1. Step 1: Understand nested pattern decoding

   The problem requires handling nested brackets and repeat counts, which demands tracking multiple levels of context.

2. Step 2: Identify approach that handles nesting efficiently

   A stack-based iterative approach uses two stacks to store counts and partial decoded strings, correctly managing nested repeats without excessive recursion or incorrect greedy expansions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach correctly decodes nested patterns like 3[a2[c]] -> accaccacc [OK]

Hint: Nested repeats require stack to track context [OK]

Common Mistakes:

• Assuming greedy expansion works for nested patterns
• Using recursion without proper state tracking

4. You are given a binary matrix and need to find the largest rectangle containing only 1s. Which approach guarantees an optimal solution with O(rows * cols) time complexity?

easy

A. Use dynamic programming to store the largest rectangle ending at each cell without histogram transformation.

B. Use brute force to check all possible rectangles in the matrix.

C. Transform each row into a histogram of heights and apply a monotonic stack to find the largest rectangle in each histogram.

D. Apply a greedy approach by expanding rectangles from each cell until a zero is encountered.

Solution

1. Step 1: Understand the problem transformation

   The problem can be transformed row-wise into histograms where each element represents the height of consecutive 1s above it.

2. Step 2: Recognize the monotonic stack pattern

   For each histogram, the largest rectangle can be found efficiently using a monotonic stack that tracks indices of increasing heights.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Histogram + monotonic stack approach is standard for maximal rectangle [OK]

Hint: Transform rows to histograms and use monotonic stack [OK]

Common Mistakes:

• Trying brute force leads to O(n^4) time
• Greedy expansion fails on complex shapes
• DP without histogram misses efficient stack usage

5. Given the following Python function to find previous smaller elements, what is the output when the input array is [3, 7, 1]?

def previous_smaller_element_indexes(arr):
    stack = []
    result = []
    for i, num in enumerate(arr):
        while stack and arr[stack[-1]] >= num:
            stack.pop()
        if stack:
            result.append(arr[stack[-1]])
        else:
            result.append(-1)
        stack.append(i)
    return result

print(previous_smaller_element_indexes([3, 7, 1]))

easy

A. [-1, -1, -1]

B. [-1, 3, -1]

C. [-1, 3, 3]

D. [3, -1, -1]

Solution

1. Step 1: Trace iteration i=0, num=3

   Stack empty, append -1 to result, push index 0 -> stack=[0], result=[-1]

2. Step 2: Trace iteration i=1, num=7

   Stack top index 0 -> arr[0]=3 < 7, so append 3 to result, push index 1 -> stack=[0,1], result=[-1,3]

3. Step 3: Trace iteration i=2, num=1

   Pop while arr[stack[-1]] >= 1: arr[1]=7 >=1 pop, arr[0]=3 >=1 pop, stack empty, append -1, push index 2 -> stack=[2], result=[-1,3,-1]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Output matches expected previous smaller elements for each position [OK]

Hint: Pop all >= current to find closest smaller on left [OK]

Common Mistakes:

• Not popping equal or greater elements leads to wrong result
• Appending wrong element from stack top
• Off-by-one errors in indexing