Lab: structure problems
Four problems, each solved cleanly by a different data structure — min-stack, level-order traversal, k most frequent, and first unique character.
- Implement a min-stack with O(1) get_min using an auxiliary stack
- Implement level-order traversal of a binary tree using a queue
- Find the k most frequent elements using a heap
- Find the first unique character in a string using a dict for counts
This is an optional lab. Four problems — pick the right tool each time. Each one has a brute-force approach that works but is slower or more complicated than the idiomatic solution. The starter code sets up the structure; you fill in the logic.
Problem 1 — Min-stack with O(1) get_min
A standard stack tracks push and pop. The twist: get_min() must return the
current minimum in O(1) time — even after pops have removed previous minimums.
Think first. You cannot scan the whole stack on every get_min call —
that is O(n). Instead, track the minimum at each level of the stack. A
second "min-stack" running in parallel records what the minimum was when each
element was pushed.
Complete MinStack so that push, pop, top, and get_min all work correctly. push adds a value, pop removes the top, top returns the top without removing it, get_min returns the current minimum in O(1).
push(5), push(3), push(7), get_min() → 3push(5), push(3), pop(), get_min() → 5The min-stack mirrors every push and pop on the main stack. On each push it
records min(new_value, current_min). On pop both stacks shrink together.
get_min just reads min_stack[-1] — constant time, no scanning.
Problem 2 — Level-order traversal
Given a binary tree, return the node values level by level, as a list of
lists: [[root], [level-1 nodes], [level-2 nodes], ...].
This is BFS on a tree. The queue stores nodes; after dequeueing each node you enqueue its children.
Implement level_order(root) that returns a list of lists, where each inner list contains the values of nodes at that depth. Use a deque as the BFS queue.
level_order(tree with root 1, children 2 and 3) → [[1], [2, 3]]The key is level_size = len(queue) at the start of each outer loop
iteration. This freezes how many nodes belong to the current level. You
dequeue exactly that many, collecting their values, then move on to the next
level. Without this count you cannot separate levels cleanly.
Problem 3 — k most frequent elements
Given a list of integers, return the k elements that appear most often. If there are ties, any among the tied elements is acceptable.
Implement k_most_frequent(nums, k) returning a list of the k most frequent elements in nums. Order within the result does not matter.
k_most_frequent([1,1,1,2,2,3], 2) → [1, 2]Counter counts frequencies in O(n). heapq.nlargest(k, iterable, key=fn)
runs O(n log k) internally — it maintains a min-heap of size k while scanning.
Both pieces together stay O(n log k), which beats a full sort at O(n log n)
when k is small.
Problem 4 — First unique character
Given a string, return the index of the first character that appears exactly once. Return -1 if no such character exists.
Implement first_unique_char(s) returning the index of the first character in s that appears exactly once, or -1 if there is none.
first_unique_char("leetcode") → 0first_unique_char("aabb") → -1Two passes through the string: the first builds the frequency map in O(n), the second finds the leftmost character with count 1 in O(n). Total O(n) time and O(k) space where k is the alphabet size (at most 26 for lowercase ASCII — in practice constant). This is the "count then scan" pattern that appears in many string problems.
Done?
Four problems, four structures. The min-stack demonstrates that the right auxiliary structure can make an otherwise-expensive query free. Level-order traversal shows BFS on a tree. The frequency heap combines counting with heap selection. The unique-character problem is a clean "count then scan" pattern. Each one generalises: the min-stack idea applies to any monotone aggregate, level-order is the basis of BFS on any hierarchical data, top-K frequency appears in analytics and autocomplete, and count-then-scan solves dozens of string problems.