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. You are given an integer array and need to determine if there exists a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force triple nested loops checking all triplets

B. Greedy approach scanning from left to right picking local minima and maxima

C. Using a monotonic stack to track potential '3' and '2' values while iterating backwards

D. Dynamic programming with prefix minimum and suffix maximum arrays

Solution

1. Step 1: Understand the 132 pattern condition

   The problem requires finding a subsequence i < j < k with nums[i] < nums[k] < nums[j], which is the 132 pattern.

2. Step 2: Identify the approach that achieves O(n) time

   The monotonic stack approach iterates from right to left, maintaining candidates for the '3' and '2' elements efficiently, achieving linear time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is known optimal for 132 pattern detection [OK]

Hint: Monotonic stack solves 132 pattern in O(n) [OK]

Common Mistakes:

• Thinking brute force is acceptable for large inputs
• Confusing greedy with monotonic stack
• Assuming DP is needed

2. Given the following code snippet for decoding strings, what is the final returned string when the input is 2[ab]?

easy

A. abab

B. ab2

C. 2ab

D. aabb

Solution

1. Step 1: Trace parsing of '2[ab]'

   k accumulates 2, '[' pushes k=2 and empty string stack, current_string resets, then 'a','b' appended.

2. Step 2: On ']', pop count=2 and prev_string=[], current_string becomes [] + ['a','b']*2 = ['a','b','a','b']

   Return joined string 'abab'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected repeated substring 'abab' [OK]

Hint: Repeat count multiplies substring inside brackets [OK]

Common Mistakes:

• Misinterpreting repeat count as string
• Appending digits as characters

3. You need to implement a data structure that supports push, pop, top, and empty operations with stack semantics, but you are only allowed to use one or two FIFO queues internally. Which approach guarantees that pop and top operations run in O(1) time while push may take O(n) time?

easy

A. Use two queues where push is O(1) and pop is O(n) by transferring elements between queues.

B. Use one queue and rotate it after each push so the last pushed element is always at the front, making pop O(1).

C. Use a stack internally and simulate queues by reversing the stack on each operation.

D. Use two queues and alternate elements between them without rotation, relying on queue order to simulate stack.

Solution

1. Step 1: Understand the problem constraints

   We want stack operations but only queues are allowed internally. The goal is to optimize pop and top to O(1).

2. Step 2: Analyze approaches

   Using one queue and rotating it after each push places the newest element at the front, so pop and top are O(1). Other approaches either have costly pop or do not maintain correct order.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   One queue rotation after push -> newest element front -> O(1) pop/top [OK]

Hint: Rotate one queue after push to get O(1) pop/top [OK]

Common Mistakes:

• Assuming two queues with push O(1) and pop O(1) is possible
• Trying to simulate stack with queue without rotation
• Using stack internally which is disallowed

4. Suppose you want to implement a queue using two stacks, but now the queue must support a 'reuse' operation that re-enqueues the last dequeued element. Which modification ensures correctness and efficiency?

hard

A. Use a third stack to hold reused elements and merge it with push_stack during transfers.

B. After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation.

C. Clear both stacks and re-insert all elements including the reused element to maintain order.

D. Store the last dequeued element separately and push it back onto the push_stack when reuse is called, without changing pop_stack.

Solution

1. Step 1: Understand reuse operation

   Reuse means re-enqueueing the last dequeued element, so it should be treated as a new push.

2. Step 2: Choose efficient modification

   Storing the last popped element separately and pushing it onto push_stack on reuse preserves order and amortized efficiency.

3. Step 3: Analyze other options

   After every pop, immediately push the popped element back onto pop_stack to allow reuse, effectively making pop a peek operation, breaks queue semantics by not removing element. Clearing both stacks and re-inserting all elements including the reused element is inefficient. Using a third stack to hold reused elements and merging it with push_stack during transfers adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reuse as push to push_stack keeps order and efficiency [OK]

Hint: Reuse = push last popped element onto push_stack [OK]

Common Mistakes:

• Trying to reuse by pushing onto pop_stack
• Rebuilding stacks on reuse causing inefficiency

5. Suppose the problem changes so that elements in the array can be negative integers. Which modification to the monotonic stack approach is necessary to correctly compute the sum of subarray minimums?

hard

A. Add a sentinel element with value 0 at the end to ensure stack empties correctly

B. No change needed; the existing monotonic stack approach works for negative values

C. Use a different data structure like a balanced BST to handle negative values

D. Modify the comparison to use <= instead of < to handle negative duplicates

Solution

1. Step 1: Analyze effect of negative values on monotonic stack

   The monotonic stack approach relies on relative ordering, which holds regardless of sign.

2. Step 2: Confirm no structural changes needed

   Sentinel and strict < comparison still work; negative values do not break the logic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack handles negatives without modification [OK]

Hint: Monotonic stack compares values, sign does not affect correctness [OK]

Common Mistakes:

• Assuming negative values require different data structures
• Changing comparison operators unnecessarily