First Unique Character in a Stream

▶

Steps

setup

Initialize frequency array and queue

Create a frequency array of size 26 initialized to zero and an empty queue to hold characters.

💡 This initialization sets up the data structures needed to track character counts and candidate unique characters.

Line:

freq = [0] * 26
q = deque()

💡 The frequency array allows O(1) updates and checks for each character; the queue will maintain order of unique candidates.

fill_cells

Process first character 'a'

Process 'a', increment its frequency from 0 to 1, and since it's the first occurrence, push it into the queue.

💡 Adding a new unique character to the queue is crucial to track potential first unique characters.

Line:

idx = ord(ch) - ord('a')
freq[idx] += 1
if freq[idx] == 1:
    q.append(ch)

💡 'a' is now the only unique character and is at the front of the queue.

fill_cells

Process second character 'b'

Process 'b', increment its frequency from 0 to 1, and push it into the queue as it is a new unique character.

💡 New unique characters are appended to the queue to maintain order of arrival.

Line:

idx = ord(ch) - ord('a')
freq[idx] += 1
if freq[idx] == 1:
    q.append(ch)

💡 Queue now holds ['a', 'b'], with 'a' still the first unique character.

fill_cells

Process third character 'c'

Process 'c', increment its frequency from 0 to 1, and push it into the queue as a new unique character.

💡 Each new unique character is added to the queue to maintain candidates for first unique.

Line:

idx = ord(ch) - ord('a')
freq[idx] += 1
if freq[idx] == 1:
    q.append(ch)

💡 Queue now holds ['a', 'b', 'c'], 'a' remains first unique.

compare

Process fourth character 'a' (repeat)

Process 'a' again, increment its frequency from 1 to 2. Since 'a' frequency > 1, pop it from the front of the queue.

💡 Removing characters with frequency > 1 keeps the queue only with unique candidates.

Line:

freq[idx] += 1
while q and freq[ord(q[0]) - ord('a')] > 1:
    q.popleft()

💡 'a' is no longer unique, so it is removed from the queue.

compare

Process fifth character 'c' (repeat)

Process 'c' again, increment its frequency from 1 to 2. Since 'c' frequency > 1, pop it from the front of the queue until front is unique.

💡 Repeated characters are removed from the queue to maintain only unique candidates.

Line:

freq[idx] += 1
while q and freq[ord(q[0]) - ord('a')] > 1:
    q.popleft()

💡 'c' is no longer unique and must be removed; 'b' remains unique so queue front is 'b'.

compare

Process sixth character 'b' (repeat)

Process 'b' again, increment its frequency from 1 to 2. Since 'b' frequency > 1, pop it from the front of the queue, which empties the queue.

💡 When the queue becomes empty, it means no unique characters remain at this point.

Line:

freq[idx] += 1
while q and freq[ord(q[0]) - ord('a')] > 1:
    q.popleft()

💡 No unique characters remain, so answer is '#'.

fill_cells

Process seventh character 'd'

Process 'd', increment its frequency from 0 to 1, and push it into the queue as a new unique character.

💡 New unique characters after empty queue restart the queue with fresh candidates.

Line:

freq[idx] += 1
if freq[idx] == 1:
    q.append(ch)

💡 'd' is now the first unique character in the stream.

reconstruct

Prepare to compile final result

All characters processed; prepare to compile the final list of first unique characters after each insertion.

💡 Separating compilation step clarifies the final output construction.

Line:

result = [...]  # collected during processing

💡 The result list is ready and matches the expected output.

reconstruct

Compile final result

After processing all characters, the result list contains the first unique character after each insertion.

💡 The result list shows the dynamic updates of the first unique character as the stream progresses.

Line:

return result

💡 The algorithm efficiently tracks the first unique character at each step without rescanning the stream.

from collections import deque

def first_unique_stream(stream):
    freq = [0] * 26  # STEP 1: Initialize frequency array
    q = deque()      # STEP 1: Initialize queue
    result = []
    for i, ch in enumerate(stream):
        idx = ord(ch) - ord('a')  # STEP 2+: Calculate index
        freq[idx] += 1            # STEP 2+: Increment frequency
        if freq[idx] == 1:        # STEP 2+: If first occurrence
            q.append(ch)          # STEP 2+: Push to queue
        while q and freq[ord(q[0]) - ord('a')] > 1:  # STEP 5: Remove non-unique
            q.popleft()           # STEP 5: Pop from queue
        result.append(q[0] if q else '#')  # STEP 6: Append first unique or '#'
    return result

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

📊

First Unique Character in a Stream - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals how the queue and frequency array work together to efficiently track the first unique character in a stream, which is difficult to grasp by reading code alone.

no_op

Stack (top→bottom)

empty

pushElement[0]: a

Stack (top→bottom)

a

↑ pushed: a

Contributes: "a"

pushElement[1]: b

Stack (top→bottom)

b

a

↑ pushed: b

Contributes: "a"

pushElement[2]: c

Stack (top→bottom)

c

b

a

↑ pushed: c

Contributes: "a"

popElement[3]: a

Stack (top→bottom)

c

b

↓ popped: [a]

Contributes: "b"

popElement[4]: c

Stack (top→bottom)

b

↓ popped: [c]

Contributes: "b"

popElement[5]: b

Stack (top→bottom)

empty

↓ popped: [b]

Contributes: "#"

pushElement[6]: d

Stack (top→bottom)

d

↑ pushed: d

Contributes: "d"

no_opElement[6]: d

Stack (top→bottom)

d

Contributes: ["a","a","a","b","b","#","d"]

no_opElement[6]: d

Stack (top→bottom)

d

Contributes: ["a","a","a","b","b","#","d"]

Key Takeaways

✓ The queue always holds characters with frequency exactly 1, ensuring the front is the first unique character.

This property is hard to see from code alone because it requires understanding the interplay of frequency updates and queue pops.

✓ When a character repeats, it is removed from the queue, dynamically updating the first unique character without rescanning the stream.

Visualizing the queue popping repeated characters clarifies how the algorithm maintains efficiency.

✓ If the queue becomes empty, it means no unique characters remain, and the algorithm returns '#'.

This condition is subtle and critical to handle correctly, and the visualization shows exactly when and why it happens.

Practice

1. You are given a list of asteroids represented by integers where the absolute value represents size and the sign represents direction (positive moving right, negative moving left). When two asteroids moving in opposite directions collide, the smaller one explodes. Which algorithmic approach guarantees an optimal solution to determine the state of asteroids after all collisions?

easy

A. Sorting asteroids by size and simulating collisions from largest to smallest

B. Greedy approach that removes pairs of colliding asteroids in a single pass without revisiting previous elements

C. Dynamic programming that stores subproblems of asteroid states to avoid recomputation

D. Stack simulation that processes asteroids sequentially, resolving collisions by comparing the current asteroid with the top of the stack

Solution

1. Step 1: Understand the collision condition

   Collisions only happen when a right-moving asteroid (positive) meets a left-moving asteroid (negative) coming after it.

2. Step 2: Recognize stack simulation suitability

   A stack naturally models the sequence of asteroids and allows checking the last asteroid's direction and size to resolve collisions efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach handles direction and size checks correctly [OK]

Hint: Stack simulates collisions by tracking last asteroid [OK]

Common Mistakes:

• Assuming greedy single pass without stack handles all cases
• Using DP unnecessarily
• Sorting breaks order-dependent collisions

2. 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

3. You need to implement a data structure that supports enqueue and dequeue operations using only stack operations (push and pop). Which approach guarantees an amortized O(1) time complexity per operation?

easy

A. Use two stacks: push elements onto one stack, and pop elements from the other stack, transferring elements only when the pop stack is empty.

B. Use a single stack and recursion to simulate dequeue by popping all elements and restoring them after retrieving the front.

C. Use two stacks and transfer elements from push stack to pop stack on every push operation to keep pop stack always ready.

D. Use a queue internally and simulate stacks by reversing the order on every operation.

Solution

1. Step 1: Understand the problem constraints

   The goal is to implement a queue using stacks with efficient enqueue and dequeue operations.

2. Step 2: Analyze approaches for efficiency

   Approach A uses two stacks and transfers elements only when the pop stack is empty, achieving amortized O(1) per operation. Approach B uses recursion and is O(n) per pop. Approach C transfers on every push, causing O(n) per push. Approach D is unrelated and inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two stacks with lazy transfer -> amortized O(1) [OK]

Hint: Two stacks with lazy transfer gives amortized O(1) [OK]

Common Mistakes:

• Thinking transferring on every push is optimal
• Using recursion causing O(n) pop

4. You need to design a data structure that supports push, pop, top, and retrieving the minimum element in constant time. Which approach guarantees all operations run in O(1) time without scanning the entire stack for the minimum each time?

easy

A. Use a brute force stack and scan the entire stack to find the minimum on each getMin call.

B. Use a dynamic programming table to store minimums for all sub-stacks and update it on each push/pop.

C. Keep two stacks: one for all elements and one for minimum elements, pushing to the min stack only when a new minimum is found.

D. Maintain a single stack that stores the difference between the pushed value and the current minimum, updating the minimum accordingly.

Solution

1. Step 1: Understand the problem constraints

   The goal is to achieve O(1) time for all operations including getMin, without scanning the entire stack.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n), dynamic programming is unnecessary and inefficient, two stacks approach works but uses extra space. The single stack with encoded differences stores relative values and updates min in O(1) time and space efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single stack encoding achieves O(1) time and O(n) space with one stack [OK]

Hint: Single stack encoding stores differences for O(1) min retrieval [OK]

Common Mistakes:

• Thinking scanning stack for min is acceptable
• Confusing two-stack approach as optimal space
• Assuming DP is needed for min tracking

5. Given the following Python code for checking valid parentheses, what is the return value when the input string is "([)]"?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

easy

A. False

B. True

C. Raises an exception

D. Depends on input length

Solution

1. Step 1: Trace input "([)]" through the code

   Push '(' then push '['. Next char is ')', expected to match '[' but pairs[')'] = '(', top of stack is '[' -> mismatch -> return False immediately.

2. Step 2: Confirm final output

   Function returns False as soon as mismatch is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mismatch detected at third character -> returns False [OK]

Hint: Mismatch causes immediate False return [OK]

Common Mistakes:

• Assuming order doesn't matter and returning True incorrectly