# Linked Lists, Stacks, Monotonic Queues, Binary Search & Heaps

> Core data structures and algorithmic patterns for coding interviews covering Floyd's Cycle Detection proof, in-place Linked List manipulation, LRU & LFU Cache internals, Monotonic Stacks (Next Greater Element, Largest Rectangle in Histogram), Monotonic Deques, Binary Search on Answer Space, O(n) Heapify proof, Quickselect, and Two Heaps.

- **Canonical URL:** https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc/
- **Markdown URL:** https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc.md
- **Level:** basic
- **Languages:** en → en
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | How do you perform Binary Search in a Rotated Sorted Array (`LeetCode 33`) in $O(\log n)$ time? | At any `mid = (lo + hi) // 2`, splitting a rotated sorted array with distinct elements guarantees that **at least one half (`[lo..mid]` or `[mid..hi]`) is strictly sorted**! Check `if nums[lo] <= nums[mid]`: then the left half is sorted—if `nums[lo] <= target < nums[mid]`, search left (`hi = mid - 1`), else search right (`lo = mid + 1`). Otherwise (`nums[lo] > nums[mid]`), the right half `[mid..hi]` is sorted—if `nums[mid] < target <= nums[hi]`, search right (`lo = mid + 1`), else search left (`hi = mid - 1`). |  |  |
| 2 | How do you solve 'Basic Calculator II' (`+`, `-`, `*`, `/`, `LeetCode 227`) in $O(n)$ time and $O(1)$ space without a full Shunting-Yard stack? | Track `total = 0`, `last_term = 0`, `curr_num = 0`, and `prev_op = '+'`. When encountering the next operator (or end of string), apply `prev_op` to `curr_num`: if `+`, add `last_term` to `total` and set `last_term = +curr_num`; if `-`, add `last_term` to `total` and set `last_term = -curr_num`; if `*`, update `last_term = last_term * curr_num`; if `/`, update `last_term = int(last_term / curr_num)` (truncating toward zero). Finally return `total + last_term`. |  |  |
| 3 | Explain the 'Binary Search on the Answer Space' pattern (`Koko Eating Bananas` `LC 875`, `Capacity To Ship Packages` `LC 1011`, `Split Array Largest Sum` `LC 410`). | Whenever a problem asks for the **Minimum $X$ such that `feasible(X)` is True** (or Maximum $X$), and `feasible(X)` is a **monotonic predicate** (i.e., if capacity/speed $X$ works, then any $X' > X$ also works: `[False, False, ..., True, True]`), binary search directly over the range of possible answers `[min_possible_ans, max_possible_ans]`! For `Split Array Largest Sum` (`LC 410`), `lo = max(nums)`, `hi = sum(nums)`, and `feasible(max_sum)` greedily counts in $O(n)$ if the array can be split into $\le k$ subarrays each summing to $\le \text{max\_sum}$. |  |  |
| 4 | Compare the K-Way Merge pattern (`Merge k Sorted Lists` `LeetCode 23`, `Smallest Range Covering Elements from K Lists` `LeetCode 632`) using a Min-Heap vs. Divide-and-Conquer. | Given $K$ sorted lists with $N$ total elements: 1. Min-Heap of size $K$: Push the head of each of the $K$ non-empty lists `(node.val, list_idx, node)` into the Min-Heap; repeatedly `heappop` the smallest node, append it to result, and if `node.next` exists, `heappush` `node.next`—runs in $O(N \log K)$ time and $O(K)$ heap space. 2. Divide-and-Conquer pairwise merge: Merge list $0$ with $1$, $2$ with $3$, etc. across $\log_2 K$ rounds—also $O(N \log K)$ time and $O(1)$ space. |  |  |
| 5 | How do you schedule tasks with a cooldown period $n$ (`Task Scheduler`, `LeetCode 621`) using either a Max-Heap + Cooldown Queue or the $O(N)$ Greedy Math formula? | Simulation: Use a Max-Heap of remaining frequencies and a FIFO Queue `(ready_freq, available_time)` holding tasks currently cooling down. Math Formula ($O(N)$ time, $O(1)$ space for 26 letters): Let `max_f` be the highest frequency of any task, and `num_max` be how many distinct tasks tie for `max_f`. Arrange the `max_f` occurrences as `max_f - 1` chunks of length `n + 1` plus a final cap of `num_max`: `ans = max(len(tasks), (max_f - 1) * (n + 1) + num_max)`. |  |  |
| 6 | How does a Monotonic Increasing Stack solve 'Largest Rectangle in Histogram' (`LeetCode 84`) in $O(n)$ time? | For each bar `h = heights[idx]`, the widest rectangle of height `h` extends left to the Previous Smaller Element (`PSE`) and right to the Next Smaller Element (`NSE`). Maintain a **monotonically increasing** stack of indices (append a sentinel height `0` at the end of `heights` to flush all remaining bars). When `heights[i] < heights[stack[-1]]`, pop `top = stack.pop()`: its height is `H = heights[top]`, its right boundary (exclusive) is `i`, its left boundary (exclusive) is `stack[-1]` (or `-1` if stack is empty), so `width = i - stack[-1] - 1` and `area = H * width`! |  |  |
| 7 | How do you check if a Singly Linked List is a Palindrome (`LeetCode 234`) or `Reorder List` (`L0 -> Ln -> L1 -> Ln-1`, `LeetCode 143`) in $O(n)$ time and $O(1)$ space? | Both problems share the same 3-step $O(1)$-space composition: 1. Find the middle of the linked list using `slow` (`+1`) and `fast` (`+2`) pointers; 2. Reverse the second half of the linked list in-place starting at `slow.next` (and sever `slow.next = None`); 3. Walk two pointers from `head` and the reversed second half simultaneously—either comparing values for Palindrome (then optionally re-reversing to restore the list) or alternatingly weaving nodes (`first.next = second; second.next = tmp1`) for `Reorder List`. |  |  |
| 8 | Compare `bisect_left` (`std::lower_bound`) and `bisect_right` (`std::upper_bound`) in Binary Search, and write the bug-free half-open `[lo, hi)` template. | Using half-open interval `lo = 0, hi = len(nums)`: while `lo < hi`: compute `mid = lo + (hi - lo) // 2` (avoids 32-bit integer overflow in C++/Java). For `bisect_left` (first index where `nums[idx] >= target`): `if nums[mid] < target: lo = mid + 1 else: hi = mid`. For `bisect_right` (first index where `nums[idx] > target`): `if nums[mid] <= target: lo = mid + 1 else: hi = mid`. Both terminate with `lo == hi` at the exact insertion boundary, and `bisect_right(x) - bisect_left(x)` equals the count of `x` in the sorted array! |  |  |
| 9 | Compare the three approaches to finding the 'Kth Largest Element in an Array' (`LeetCode 215`): Sorting, Min-Heap of size $K$, and Quickselect. | 1. Sorting: $O(n \log n)$ time, $O(1)$ or $O(n)$ space. 2. Min-Heap of size $K$ (keep the $K$ largest seen so far; whenever `len(heap) > K`, `heappop` the smallest—at the end `heap[0]` is the $K$-th largest!): $O(n \log K)$ time, $O(K)$ space (ideal for streaming data). 3. Quickselect (Hoare's selection using random pivot + 3-way Dutch National Flag partition to handle duplicates): Recurse only into the partition containing index $n - K$; $O(n)$ average time ($T(n) = T(n/2) + O(n)$), $O(n^2)$ worst-case, $O(1)$ space. |  |  |
| 10 | What is the iterative 3-pointer pattern for reversing a singly linked list in-place (`LeetCode 206`), and why is a `dummy` sentinel node useful in `Reverse Nodes in k-Group` (`LeetCode 25`)? | To reverse in-place: initialize `prev = None, curr = head`; while `curr`: save `nxt = curr.next`, reverse pointer `curr.next = prev`, advance `prev = curr`, and `curr = nxt` (returns `prev`). In problems where the `head` node itself changes (such as `Reverse Nodes in k-Group`, `Remove Nth Node From End`, or `Partition List`), prepending `dummy = ListNode(0, head)` eliminates all special-case `if head` branching—you simply return `dummy.next`. |  |  |
| 11 | Prove mathematically why Floyd's Tortoise and Hare algorithm (`LeetCode 142 Linked List Cycle II`) finds the exact cycle entry node when resetting one pointer to `head`. | Let $L$ be the distance from `head` to the cycle entry, $C$ be the cycle length, and $x$ be the distance from the cycle entry to the meeting point inside the cycle. When `slow` (1x speed) and `fast` (2x speed) meet: $2 \cdot d_{\text{slow}} = d_{\text{fast}} \implies 2(L + x) = L + x + kC \implies L + x = kC \implies L = kC - x = (k-1)C + (C - x)$. Since $(C - x)$ is the remaining distance from the meeting point forward to the cycle entry, advancing one pointer from `head` ($L$ steps) and the other from the meeting point at 1x speed guarantees they collide at the exact cycle entry! |  |  |
| 12 | How do you solve 'Top K Frequent Elements' (`LeetCode 347`) in $O(n)$ linear time using Bucket Sort? | 1. Count frequencies of each element using a Hash Map `count` in $O(n)$ time. 2. Since no element in an array of length $n$ can appear more than $n$ times, create an array `buckets` of $n + 1$ empty lists where `buckets[freq]` holds all numbers appearing `freq` times. 3. Iterate `freq` backwards from $n$ down to `1`, collecting elements from `buckets[freq]` until $K$ elements are gathered—running in $O(n)$ time and $O(n)$ space! |  |  |
| 13 | How can you reduce 'Maximal Rectangle' of `1`s in a 2D binary matrix (`LeetCode 85`) to 'Largest Rectangle in Histogram'? | Process the $R \times C$ binary matrix row by row from top to bottom, maintaining a 1D array `heights` of length $C$: for each column $c$, if `matrix[r][c] == '1'`, increment `heights[c] += 1`, else reset `heights[c] = 0`. After updating `heights` for row $r$, run the $O(C)$ Monotonic Stack 'Largest Rectangle in Histogram' algorithm on `heights`, yielding an overall $O(R \times C)$ time and $O(C)$ space solution. |  |  |
| 14 | Prove why Floyd's bottom-up `heapify` (`heapq.heapify(arr)`) builds a Binary Heap in $O(n)$ time rather than $O(n \log n)$. | Bottom-up `heapify` calls `sift_down` starting from the last non-leaf node $\lfloor n/2 \rfloor - 1$ down to `0`. A node at height $h$ above the leaves performs at most $h$ swaps, and there are at most $\lceil n / 2^{h+1} \rceil$ nodes at height $h$. Total work is $\sum_{h=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^{h+1}} O(h) = O\left(n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}}\right)$. Since the infinite series $\sum_{h=1}^{\infty} \frac{h}{2^h} = 2$ converges to a constant, total build time is strictly $O(n)$! (Whereas inserting $n$ items one-by-one via top-down `sift_up` moves the $n/2$ bottom leaves up $\log n$ levels, taking $O(n \log n)$). |  |  |
| 15 | How do you implement a Queue using Two Stacks (`LeetCode 232`) with $O(1)$ amortized `push`, `pop`, and `peek`? | Maintain an `in_stack` and an `out_stack`. `push(x)` always pushes onto `in_stack` in $O(1)$ worst-case time. For `pop()` or `peek()`: if `out_stack` is non-empty, simply pop/peek from `out_stack` in $O(1)$ time; ONLY when `out_stack` is completely empty, transfer all elements from `in_stack` into `out_stack` (`while in_stack: out_stack.append(in_stack.pop())`), which reverses their LIFO order into FIFO order! Each element is pushed and popped at most twice across its lifetime ($O(1)$ amortized). |  |  |
| 16 | How does the Two-Heaps pattern find the Running Median from a Data Stream (`LeetCode 295`) in $O(\log n)$ per insertion and $O(1)$ per query? | Maintain two heaps: 1. `small` (a **Max-Heap** storing the smaller half of numbers; in Python `heapq`, negate values `-x`), and 2. `large` (a **Min-Heap** storing the larger half of numbers). Maintain two invariants: (a) Every element in `small` $\le$ every element in `large` (push new `x` to `small`, then pop max from `small` and push to `large`); (b) Sizes differ by at most 1 (`len(small) == len(large)` or `len(small) == len(large) + 1`). Then the median is `-small[0]` (if odd) or `(-small[0] + large[0]) / 2.0` (if even) in $O(1)$ time! |  |  |
| 17 | How do you extend the Two-Heaps pattern with 'Lazy Deletion' to solve 'Sliding Window Median' (`LeetCode 480`) in $O(n \log k)$ time? | Removing an outgoing element `nums[i - k]` from an arbitrary position inside a Binary Heap takes $O(k)$ time unless we use **Lazy Deletion**: maintain a Hash Map `delayed` counting elements that have exited the window, and track the logical size (`valid_small`, `valid_large`) of each heap (decrementing the logical size of whichever heap holds the outgoing element). Only actually `heappop` elements from `small` or `large` when a `delayed` element rises to the very top (`heap[0]`) of either heap! |  |  |
| 18 | How does a `Min Stack` (`LeetCode 155`) support `push`, `pop`, `top`, and `getMin` in $O(1)$ time? | Store pairs `(val, current_min)` on the stack (or maintain a parallel `min_stack` that only pushes when `val <= min_stack[-1]`): at each `push(val)`, the new `current_min` is `min(val, stack[-1][1])`. Because stack additions/removals follow LIFO order, the minimum of all elements below any stack depth is invariant until that element itself is popped! |  |  |
| 19 | How is a Binary Heap represented in a flat 0-indexed array, and what are the parent/child index formulas? | A Binary Heap is a Complete Binary Tree (every level is completely filled except possibly the bottom level, which is filled strictly from left to right), allowing compact storage in a 0-indexed array with zero pointer overhead: For any node at index $i$: `parent(i) = (i - 1) // 2`; `left_child(i) = 2 * i + 1`; `right_child(i) = 2 * i + 2`. All leaf nodes sit at indices $\lfloor n/2 \rfloor \dots n - 1$. |  |  |
| 20 | Explain the Monotonic Stack pattern and how it finds the `Next Greater Element` (or `Daily Temperatures`, `LeetCode 739`) for every element in $O(n)$ time. | Maintain a stack of array indices whose values are in **monotonically decreasing** order from bottom to top. As you iterate `i` from `0` to `n - 1`: `while stack and nums[i] > nums[stack[-1]]:` pop `prev_idx = stack.pop()`—then `nums[i]` is the first strictly greater element to the right of `prev_idx` (`ans[prev_idx] = i - prev_idx`)! Then push `i` onto `stack`. Because each index is pushed once and popped at most once, the amortized time across all $n$ elements is $O(n)$. |  |  |
| 21 | How do you find the intersection node of two singly linked lists (`LeetCode 160`) in $O(m + n)$ time and $O(1)$ space without calculating lengths first? | Initialize `pA = headA` and `pB = headB`. At each step, advance `pA = pA.next if pA else headB` and `pB = pB.next if pB else headA`. Why it works: if the lists have lengths $a + c$ and $b + c$ (where $c$ is the shared tail), both pointers travel the exact same total distance $a + c + b$ before meeting at the intersection node (or both reach `None` simultaneously at distance $m + n$ if $c = 0$). |  |  |
| 22 | How does a Monotonic Deque solve 'Sliding Window Maximum' (`LeetCode 239`) in $O(n)$ time instead of $O(n \log k)$ with a Heap? | Maintain a double-ended queue (`collections.deque`) storing **indices** of elements in the current window in **strictly decreasing** order of their values (`nums[dq[0]]` is always the window maximum). At each index `i`: 1. Evict from back (`while dq and nums[dq[-1]] <= nums[i]: dq.pop()`) because an older, smaller element can NEVER be a future window maximum now that `nums[i]` is present! 2. Append `i` to back (`dq.append(i)`). 3. Evict expired index from front if outside window (`if dq[0] <= i - k: dq.popleft()`). 4. If `i >= k - 1`, record `nums[dq[0]]`. |  |  |
| 23 | How do you solve 'Kth Smallest Element in a Sorted Matrix' (`LeetCode 378`) or 'Find K Pairs with Smallest Sums' (`LeetCode 373`) using a Min-Heap? | Treat each of the first $\min(R, K)$ rows as a sorted list: push `(matrix[r][0], r, 0)` into the Min-Heap (or simply start with `(matrix[0][0], 0, 0)` if deduplicating visited cells), and pop $K$ times—each time popping `(val, r, c)` and pushing `(matrix[r][c + 1], r, c + 1)`, running in $O(K \log(\min(R, K)))$ time. (Alternatively, `LC 378` can be solved in $O((R + C) \log(\text{max} - \text{min}))$ time and $O(1)$ space via Binary Search on Value Range using a bottom-left staircase count!). |  |  |
| 24 | How do you design an `LFU Cache` (Least Frequently Used, `LeetCode 460`) with strict $O(1)$ `get` and `put` operations? | Maintain: 1. `key_to_node` Hash Map (`key -> Node(key, val, freq)`); 2. `freq_to_dll` Hash Map (`freq -> DoublyLinkedList` of nodes currently having that exact access frequency, ordered by recency to break ties via LRU); and 3. An integer `min_freq` tracking the lowest existing frequency. On `get(key)` or update: remove `node` from `freq_to_dll[f]`, increment `node.freq` to `f + 1`, append to `freq_to_dll[f + 1]`, and if `f == min_freq` and `freq_to_dll[f]` is now empty, increment `min_freq += 1`. On new key insertion when full: evict the LRU node from `freq_to_dll[min_freq]` and reset `min_freq = 1`. |  |  |
| 25 | How do you solve 'Find Peak Element' (`LeetCode 162`) in $O(\log n)$ time on an unsorted array? | Given boundary conditions `nums[-1] = nums[n] = -inf` and `nums[i] != nums[i+1]`, compare `nums[mid]` with its right neighbor `nums[mid + 1]`: if `nums[mid] < nums[mid + 1]`, we are on a rising slope—since the right boundary eventually drops to `-inf`, a peak is GUARANTEED to exist in `[mid + 1 .. hi]`, so `lo = mid + 1`. Otherwise (`nums[mid] > nums[mid + 1]`), a peak is guaranteed to exist in `[lo .. mid]`, so `hi = mid`. |  |  |
| 26 | How do you deep-copy a Linked List with `next` and arbitrary `random` pointers (`LeetCode 138`) in $O(n)$ time and $O(1)$ auxiliary space (without a Hash Map)? | Use the 3-Pass Interweaving Trick: Pass 1: For every original node `A`, insert its cloned node `A'` immediately after it (`A -> A' -> B -> B'`). Pass 2: Set random pointers on the clones using the adjacent mapping: `if curr.random: curr.next.random = curr.random.next`. Pass 3: Unweave the list to restore original `next` pointers (`A -> B`) and extract the cloned list (`A' -> B'`). |  |  |
| 27 | How do you find the 'Median of Two Sorted Arrays' (`LeetCode 4`) of sizes $m$ and $n$ in $O(\log(\min(m, n)))$ time? | Ensure `A` is the shorter array ($m \le n$). Binary search on the partition cut $i \in [0, m]$ in `A`, which automatically fixes the partition cut $j = \lfloor(m + n + 1)/2\rfloor - i$ in `B` so the left half has $\lfloor(m+n+1)/2\rfloor$ total elements. A valid partition requires `A_left <= B_right` AND `B_left <= A_right` (using `-inf` / `+inf` for out-of-bounds). If `A_left > B_right`, move cut left (`hi = i - 1`); if `B_left > A_right`, move cut right (`lo = i + 1`). Once valid, median is `max(A_left, B_left)` (odd total) or `(max(A_left, B_left) + min(A_right, B_right)) / 2` (even). |  |  |
| 28 | How does a Monotonic Stack solve 'Remove K Digits' (`LeetCode 402`) to produce the smallest possible number in $O(n)$ time? | The most significant digits on the left determine the magnitude of a number. Maintain a **monotonically non-decreasing** stack of digits: as you iterate over each digit `d` in `num`, `while k > 0 and stack and stack[-1] > d: stack.pop(); k -= 1`, then `stack.append(d)`. After the loop, if `k > 0` (e.g., input was already ascending like `"1234"`), slice off the last `k` digits (`stack = stack[:-k]`), strip leading zeros (`lstrip('0')`), and return `'0'` if empty. |  |  |
| 29 | Why does 'Search in Rotated Sorted Array II' with duplicates (`LeetCode 81`) degrade to $O(n)$ worst-case time? | When duplicate values exist, we can encounter `nums[lo] == nums[mid] == nums[hi]` (for example, `[1, 1, 1, 0, 1]` vs. `[1, 0, 1, 1, 1]`), making it impossible to tell in $O(1)$ time whether the pivot `0` lies in the left half or the right half! When `nums[lo] == nums[mid] == nums[hi]`, the only safe step is to shrink `lo += 1` and `hi -= 1`, which takes $O(n)$ in the worst case while remaining $O(\log n)$ on average. |  |  |
| 30 | How do you design an `LRU Cache` (`LeetCode 146`) where both `get(key)` and `put(key, value)` run in strict $O(1)$ time? | Combine a **Hash Map** (`key -> Node*`) with a **Doubly Linked List** bounded by two sentinel dummy nodes (`head` and `tail`). The Hash Map provides $O(1)$ lookup of any node by key; the Doubly Linked List allows removing a node from the middle (`node.prev.next = node.next; node.next.prev = node.prev`) and inserting it at the Most-Recently-Used (MRU) end in $O(1)$ time (a singly linked list would take $O(n)$ to find `prev`!). On capacity overflow, evict `head.next` (or `tail.prev`, the Least-Recently-Used node) and delete its `node.key` from the Hash Map (which is why each DLL `Node` must store BOTH `key` and `val`!). |  |  |
| 31 | How do you find the Minimum in a Rotated Sorted Array (`LeetCode 153`) using `nums[mid]` vs. `nums[hi]`? | Always compare `nums[mid]` against `nums[hi]` (NOT `nums[lo]`!). While `lo < hi`: `mid = (lo + hi) // 2`. If `nums[mid] > nums[hi]`, the minimum pivot MUST lie strictly to the right of `mid`, so `lo = mid + 1`. Otherwise (`nums[mid] < nums[hi]`), `mid` is in the lower sorted segment (and could itself be the minimum), so `hi = mid`. Loop terminates at `lo == hi` pointing to the minimum element. |  |  |
| 32 | Which non-linked-list array problem can be solved in $O(n)$ time and $O(1)$ space using Floyd's Cycle Detection without modifying the array (`LeetCode 287 Find the Duplicate Number`)? | Given an array `nums` of $n + 1$ integers where each value is in $[1, n]$, treat the array as a functional directed graph $i \to \text{nums}[i]$ starting from index `0` (which has in-degree 0 since no value is 0). Because two indices point to the same duplicate value $v$, node $v$ has in-degree $\ge 2$, forming the entry point of a cycle! Run Floyd's `slow = nums[slow]` and `fast = nums[nums[fast]]` until they meet, then reset `slow = 0` and step both by 1 (`slow = nums[slow]; fast = nums[fast]`) until they meet at the duplicate number. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/51725164-b515-42e0-a6b2-850f1d36f3fc/).