Hard Mix Problem Set

This is the finale. Every pattern from Phases 1 through 9 shows up here in disguise: a monotonic stack pretending to be a rainwater simulation, binary search pretending to be a “find the median” problem, a min-heap pretending to be a linked-list merge. If you can recognize the pattern underneath the unfamiliar wording, these hard problems stop being scary and become “oh, it’s just X.”

How to use this set

Same drill as every problem set: read the problem, name the pattern before you touch the keyboard, then fill in the stub. Each one has a # TODO and a pass that will fail the sample asserts until you replace it. Hit Run to check your output against the # expect comments, and open Show solution if you get stuck for more than a few minutes — there’s no shame in reading a solution and then re-typing it yourself from memory. When you’re happy, go solve the real version on LeetCode; the playground here only has Python’s standard library; no heapq tricks are missing, but there’s no real judge, so treat a passing local run as “ready to submit,” not “already accepted.”

1. Trapping Rain Water — LC 42 — Hard

Open LC 42 on LeetCode

Pattern: Two Pointers

Problem. Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

1 <= n <= 20000
0 <= height[i] <= 100000

trapping_rain_water.py

def trap(height):
    # TODO: two pointers from both ends. Water above index i is bounded by
    # the SMALLER of the tallest bar seen so far on the left or the right.
    pass
 
 
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # expect 6
print(trap([4, 2, 0, 3, 2, 5]))                     # expect 9

Show solution

trapping_rain_water_solution.py

def trap(height):
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
 
    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]     # left_max is the binding wall
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]    # right_max is the binding wall
 
    return water
 
 
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 6
print(trap([4, 2, 0, 3, 2, 5]))                     # 9

Why it works: water above index i is min(max_left, max_right) - height[i]. Whichever side currently has the smaller running max is guaranteed to be the binding wall for its own pointer — so you can move that pointer and settle its water amount immediately, without ever knowing the exact max on the far side.

Complexity: Time $O(n)$ , Space $O(1)$ .

2. Median of Two Sorted Arrays — LC 4 — Hard

Open LC 4 on LeetCode

Pattern: Binary Search on Answer

Problem. Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the two arrays combined, in better than $O(m + n)$ time.

0 <= m, n <= 1000, 1 <= m + n <= 2000

median_two_sorted_arrays.py

def find_median_sorted_arrays(nums1, nums2):
    # TODO: binary search on HOW MANY elements to take from the shorter
    # array so the combined left half and right half are balanced and
    # every left element <= every right element.
    pass
 
 
print(find_median_sorted_arrays([1, 3], [2]))       # expect 2.0
print(find_median_sorted_arrays([1, 2], [3, 4]))    # expect 2.5

Show solution

median_two_sorted_arrays_solution.py

def find_median_sorted_arrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1     # binary search on the SHORTER array
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    half = (m + n + 1) // 2
 
    while lo <= hi:
        i = (lo + hi) // 2      # elements taken from nums1's left half
        j = half - i            # elements taken from nums2's left half
 
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
 
        if left1 <= right2 and left2 <= right1:
            if (m + n) % 2 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2.0
        elif left1 > right2:
            hi = i - 1     # took too much from nums1, shrink i
        else:
            lo = i + 1     # took too little from nums1, grow i
 
    return 0.0
 
 
print(find_median_sorted_arrays([1, 3], [2]))       # 2.0
print(find_median_sorted_arrays([1, 2], [3, 4]))    # 2.5

Why it works: the median only needs the combined array split into a left half and a right half of (near-)equal size where every left element is <= every right element. Binary searching i (the cut point in the shorter array) fixes j (the cut point in the longer array) automatically — when left1 <= right2 and left2 <= right1, the split is valid.

Complexity: Time $O(\log(\min(m, n)))$ , Space $O(1)$ .

3. Largest Rectangle in Histogram — LC 84 — Hard

Open LC 84 on LeetCode

Pattern: Monotonic Stack

Problem. Given an array of bar heights of width 1 each, find the area of the largest rectangle that fits entirely under the histogram’s outline.

1 <= len(heights) <= 100000

largest_rectangle_histogram.py

def largest_rectangle_area(heights):
    # TODO: an increasing stack of indices. When a shorter bar arrives,
    # pop and finalize every taller bar it disqualifies -- its width runs
    # from the new top of the stack to the current index.
    pass
 
 
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))   # expect 10
print(largest_rectangle_area([2, 4]))               # expect 4

Show solution

largest_rectangle_histogram_solution.py

def largest_rectangle_area(heights):
    bars = heights + [0]     # sentinel: forces every remaining bar to pop
    stack = []                # indices, heights increasing bottom-to-top
    max_area = 0
 
    for i, h in enumerate(bars):
        while stack and bars[stack[-1]] > h:
            height = bars[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
 
    return max_area
 
 
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))   # 10  (bars of height 5,6 -> width 2)
print(largest_rectangle_area([2, 4]))               # 4

Why it works: when bar i is shorter than the bar at the top of the stack, the taller bar can never extend any further right than i - 1 — so its rectangle is final. Its width stretches back to (but not including) the new stack top, since every bar in between was at least as tall.

Complexity: Time $O(n)$ (each index is pushed and popped once), Space $O(n)$ .

4. Word Ladder — LC 127 — Hard

Open LC 127 on LeetCode

Pattern: Breadth First Search

Problem. Given begin_word, end_word, and a word_list, return the length of the shortest transformation sequence from begin_word to end_word, changing one letter at a time, where every intermediate word must exist in word_list. Return 0 if no such sequence exists.

1 <= len(begin_word) <= 10, all words the same length

word_ladder.py

from collections import deque
 
def ladder_length(begin_word, end_word, word_list):
    # TODO: BFS over words. From each word, try changing every letter at
    # every position; if the result is in the (unvisited) word set, queue
    # it with steps + 1.
    pass
 
 
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))  # expect 5
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))         # expect 0

Show solution

word_ladder_solution.py

from collections import deque
 
def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
 
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
    alphabet = "abcdefghijklmnopqrstuvwxyz"
 
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
 
        for i in range(len(word)):
            for ch in alphabet:
                candidate = word[:i] + ch + word[i + 1:]
                if candidate in words and candidate not in visited:
                    visited.add(candidate)
                    queue.append((candidate, steps + 1))
 
    return 0
 
 
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
# 5  (hit -> hot -> dot -> dog -> cog)
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))
# 0  (cog isn't in the word list)

Why it works: every word is a node, every one-letter change is an edge — and BFS on an unweighted graph guarantees the first time you reach end_word, it’s via the shortest path. Generating all 26 single-letter variants per position is the trick that builds the implicit adjacency list on the fly, without ever constructing the full graph up front.

Complexity: Time $O(N \cdot L \cdot 26)$ where N is the word count and L is the word length, Space $O(N \cdot L)$ .

5. Merge k Sorted Lists — LC 23 — Hard

Open LC 23 on LeetCode

Pattern: K-way Merge

Problem. You are given an array of k linked lists, each sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

0 <= k <= 10000, total nodes up to 10000

merge_k_sorted_lists.py

import heapq
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def merge_k_lists(lists):
    # TODO: a min-heap with one entry per non-empty list: (value, list_idx, node).
    # Pop the smallest, attach it, push its .next back in if it exists.
    pass
 
 
def build(values):
    head = ListNode(0)
    tail = head
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return head.next
 
 
def to_list(node):
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out
 
 
lists = [build([1, 4, 5]), build([1, 3, 4]), build([2, 6])]
print(to_list(merge_k_lists(lists)))   # expect [1, 1, 2, 3, 4, 4, 5, 6]

Show solution

merge_k_sorted_lists_solution.py

import heapq
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            # list_idx (i) breaks ties so two equal values never compare nodes directly
            heapq.heappush(heap, (node.val, i, node))
 
    dummy = ListNode(0)
    tail = dummy
 
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
 
    return dummy.next
 
 
def build(values):
    head = ListNode(0)
    tail = head
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return head.next
 
 
def to_list(node):
    out = []
    while node:
        out.append(node.val)
        node = node.next
    return out
 
 
lists = [build([1, 4, 5]), build([1, 3, 4]), build([2, 6])]
print(to_list(merge_k_lists(lists)))   # [1, 1, 2, 3, 4, 4, 5, 6]

Why it works: the heap holds at most one candidate per list at any time — always that list’s current smallest unconsumed node. Popping the overall minimum and pushing its successor keeps that invariant, so the output comes out sorted in a single pass over all N nodes.

Complexity: Time $O(N \log k)$ where N is the total node count and k is the number of lists, Space $O(k)$ for the heap.

6. Serialize and Deserialize Binary Tree — LC 297 — Hard

Open LC 297 on LeetCode

Pattern: Depth First Search

Problem. Design an algorithm to serialize a binary tree to a string and deserialize that string back into the same tree structure. There’s no constraint on your serialization format other than it round-trips correctly.

Up to 10000 nodes, node values in a signed 32-bit range.

serialize_deserialize_tree.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def serialize(root):
    # TODO: preorder DFS, writing "#" for every None child.
    pass
 
 
def deserialize(data):
    # TODO: consume the comma-separated tokens in the SAME preorder DFS order.
    pass
 
 
def preorder(node):
    if not node:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)
 
 
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
data = serialize(root)
print(preorder(deserialize(data)))   # expect [1, 2, 3, 4, 5]

Show solution

serialize_deserialize_tree_solution.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def serialize(root):
    tokens = []
 
    def dfs(node):
        if not node:
            tokens.append("#")
            return
        tokens.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
 
    dfs(root)
    return ",".join(tokens)
 
 
def deserialize(data):
    tokens = iter(data.split(","))
 
    def dfs():
        val = next(tokens)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left = dfs()
        node.right = dfs()
        return node
 
    return dfs()
 
 
def preorder(node):
    if not node:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)
 
 
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
data = serialize(root)
print(preorder(deserialize(data)))   # [1, 2, 3, 4, 5]

Why it works: preorder (root, then left, then right) with an explicit marker for None children is a complete, unambiguous description of the tree’s shape — unlike inorder, it doesn’t need a second traversal to disambiguate. Decoding just replays the same recursive order, consuming one token per call.

Complexity: Time $O(n)$ for both serialize and deserialize, Space $O(n)$ .

7. LRU Cache — LC 146 — Medium

Open LC 146 on LeetCode

Pattern: Linked Lists (doubly linked list + hash map)

Problem. Design a Least Recently Used (LRU) cache with a fixed capacity. Support get(key) in $O(1)$ (returns the value, or -1 if absent, and marks it as recently used) and put(key, value) in $O(1)$ (inserts or updates, evicting the least recently used entry if over capacity).

1 <= capacity <= 3000

lru_cache.py

from collections import OrderedDict
 
class LRUCache:
    def __init__(self, capacity):
        # TODO: an OrderedDict IS a doubly linked list + hash map under the
        # hood -- move_to_end() and popitem(last=False) are your two tools.
        pass
 
    def get(self, key):
        # TODO
        pass
 
    def put(self, key, value):
        # TODO
        pass
 
 
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # expect 1
cache.put(3, 3)        # evicts key 2 (least recently used)
print(cache.get(2))    # expect -1
cache.put(4, 4)        # evicts key 1
print(cache.get(1))    # expect -1
print(cache.get(3))    # expect 3
print(cache.get(4))    # expect 4

Show solution

lru_cache_solution.py

from collections import OrderedDict
 
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()   # insertion order == recency order
 
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as most recently used
        return self.cache[key]
 
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict the least recently used (front)
 
 
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1
cache.put(3, 3)        # evicts key 2
print(cache.get(2))    # -1
cache.put(4, 4)        # evicts key 1
print(cache.get(1))    # -1
print(cache.get(3))    # 3
print(cache.get(4))    # 4

Why it works: OrderedDict already tracks insertion order with $O(1)$ reordering (move_to_end) and $O(1)$ removal from either end (popitem) — exactly the doubly linked list + hash map combo the classic solution hand-rolls with a custom Node class and prev/next pointers. Both give the same $O(1)$ guarantees; OrderedDict just does the pointer bookkeeping for you.

Complexity: Time $O(1)$ for both get and put, Space $O(\text{capacity})$ .

8. Sliding Window Maximum — LC 239 — Hard

Open LC 239 on LeetCode

Pattern: Monotonic Stack (as a monotonic deque)

Problem. Given an array nums and a window size k, return an array of the maximum value in every contiguous window of size k as it slides from left to right.

1 <= k <= len(nums) <= 100000

sliding_window_maximum.py

from collections import deque
 
def max_sliding_window(nums, k):
    # TODO: a deque of INDICES, values decreasing front-to-back. Pop
    # smaller values off the back before pushing; drop the front once it
    # falls outside the window.
    pass
 
 
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))   # expect [3, 3, 5, 5, 6, 7]

Show solution

sliding_window_maximum_solution.py

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()      # indices, nums[dq[0]] .. nums[dq[-1]] strictly decreasing
    result = []
 
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()             # these can never be the max again -- num outlives them
        dq.append(i)
 
        if dq[0] <= i - k:
            dq.popleft()          # front has fallen out of the window
 
        if i >= k - 1:
            result.append(nums[dq[0]])   # front of the deque is always the window max
 
    return result
 
 
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Why it works: any value smaller than an element still inside the window and to its right can never be the max of any future window — it’s permanently dominated, so it’s discarded immediately. That keeps the deque monotonically decreasing, with the current window’s max always sitting at the front.

Complexity: Time $O(n)$ (each index pushed and popped at most once), Space $O(k)$ .

Complexity

Hard problems are usually hard because the intended bound is one class better than the obvious one, and getting there needs a specific structural insight. That insight is the last column.

#	Problem	Obvious	Intended	Space	The insight
1	Trapping Rain Water	$O(n^2)$ per-column	$O(n)$	$O(1)$ two-pointer	Water depends only on the smaller running maximum, so that side is already decided
2	Median of Two Sorted Arrays	$O(n + m)$ merge	$O(\log \min(n,m))$	$O(1)$	Binary search the split point in the shorter array, not the value
3	Largest Rectangle in Histogram	$O(n^2)$	$O(n)$	$O(n)$	A monotonic stack: each bar is pushed and popped once
4	Word Ladder	$O(N^2 L)$ pairwise	$O(N \cdot L \cdot 26)$	$O(N \cdot L)$	Generate neighbours by mutation, never by comparing word pairs
5	Merge k Sorted Lists	$O(Nk)$ sequential merge	$O(N \log k)$	$O(k)$	Heap of `k` heads — or balanced pairwise merge, same bound at $O(N)$ space
6	Serialize / Deserialize	—	$O(n)$ each way	$O(n)$	An explicit null marker is what makes the preorder string unambiguous
7	LRU Cache	$O(n)$ per op with a list	$O(1)$ per op	$O(\text{capacity})$	Hash map for lookup + doubly linked list for eviction; neither alone does both
8	Sliding Window Maximum	$O(nk)$	$O(n)$	$O(k)$	Monotonic deque of indices, so expiry is a position test

Three bounds people misstate:

Median of Two Sorted Arrays is $O(\log \min(n,m))$ , not $O(\log(n+m))$ . You binary-search the split of the shorter array, and always searching the shorter one is what gives the tighter bound.
Both monotonic-structure problems (3 and 8) are $O(n)$ amortised, with a while inside a for. Each element is pushed once and popped once. Reading the nesting as $O(n^2)$ is the usual error, and the amortised argument is the answer to “prove it”.
Merge k Sorted Lists does not require a heap. Balanced divide-and-conquer pairwise merge is also $O(N \log k)$ . The heap’s advantages are $O(k)$ space instead of $O(N)$ and that it streams — claiming the heap is asymptotically necessary is wrong, and it is a question interviewers ask.

Drills

Three micro-drills on the structural line in each of the hardest patterns here.

Drill 1 — the monotonic-stack sentinel

Drill 2 — the deque holds indices, not values

Drill 3 — serialisation needs an explicit null marker

Interview follow-ups

They ask	On which problem	The answer
“Solve it in constant space”	Trapping Rain Water	Two pointers with `left_max` and `right_max`, always advancing the side with the smaller maximum — that side’s water level is already determined. $O(1)$ , against $O(n)$ for the prefix-array and monotonic-stack versions
“Why is $O(\log(n+m))$ not the right bound?”	Median of Two Sorted Arrays	You binary-search the split point of the shorter array, so it is $O(\log \min(n,m))$ . Always choosing the shorter one is both the tighter bound and what keeps the index arithmetic in range
“Prove the stack version is $O(n)$ ”	Largest Rectangle, Sliding Window Max	Each index is pushed exactly once and popped at most once, so the total inner-loop work across the whole scan is at most `n` — the `while` inside the `for` does not multiply. This is the same amortised argument as the two-stack queue
“What is the sentinel for?”	Largest Rectangle	It forces the stack to drain so every remaining bar gets measured. Without it, an ascending input like `[1,2,3,4,5]` never pops during the scan and the answer comes back 0 instead of 9
“Why indices in the deque rather than values?”	Sliding Window Maximum	Expiry is `dq[0] <= i - k`, a question about position. With raw values there is no way to tell an aged-out entry from a live one, so the window constraint cannot be enforced
“Merge k lists without a heap”	Merge k Sorted Lists	Balanced divide-and-conquer pairwise merge: $\log k$ rounds, each touching all `N` elements, so also $O(N \log k)$ . The heap’s real edges are $O(k)$ space instead of $O(N)$ , and that it works on streams
“Why does the heap entry carry an index?”	Merge k Sorted Lists	Both to know which list to advance and to make ties comparable — `(value, node)` raises `TypeError` when two lists offer the same value, and only inputs with duplicates reveal it
“Can you serialise without null markers?”	Serialize / Deserialize	Not from preorder alone — it is ambiguous. You would need preorder plus inorder (and distinct values), or a level-order format with explicit nulls. The marker is what makes one pass sufficient
“Why does LRU need two data structures?”	LRU Cache	The map gives $O(1)$ lookup but has no order; the list gives order and $O(1)$ removal of a known node. Neither alone does both, and `prev` pointers are what make unlinking $O(1)$
“Your LRU returns correct values but fails a large test”	LRU Cache	Almost certainly `get` is not reordering. A read counts as a use, so skipping the move leaves every returned value correct and every eviction choice wrong
“Speed up Word Ladder”	Word Ladder	Bidirectional BFS from both ends, always expanding the smaller frontier — roughly a square-root reduction in nodes explored. Plus wildcard buckets (`h*t`) so neighbour generation avoids scanning the dictionary
“Return the ladder, not its length”	Word Ladder	LC 126: record parent sets per BFS level instead of a single visited set, then walk back. Meaningfully harder, and only possible because BFS proceeds level by level

Practice

Every problem on this page, generated from the problem database — so each row carries its sheet membership and reported companies, and the checkboxes remember what you have finished. The walkthroughs above are the teaching; this is the tracker.

8 problems

0 easy1 medium7 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

146LRU CachemediumNeetCode 150LeetCode Top Interview 150amazonmicrosoftbloomberggoogleuber
4Median of Two Sorted ArrayshardNeetCode 150LeetCode Top Interview 150googleamazonmicrosoftbytedance
42Trapping Rain WaterhardNeetCode 150LeetCode Top Interview 150amazongooglemetabloomberg
297Serialize and Deserialize Binary TreehardNeetCode 150Blind 75metaamazongooglebloomberg
84Largest Rectangle in HistogramhardNeetCode 150googleamazonbytedance
127Word LadderhardNeetCode 150LeetCode Top Interview 150amazongooglebytedance
239Sliding Window MaximumhardNeetCode 150amazongooglebytedance
23Merge k Sorted ListshardNeetCode 150Blind 75LeetCode Top Interview 150

Self-check

pch.quizTag pch.quizDefaultTitle

Largest Rectangle in Histogram, without the trailing 0 sentinel. What does it return for [1, 2, 3, 4, 5]?

pch.quizShowAnswer

B — 0 -- nothing ever pops during an ascending scan, so no rectangle is ever measured — Verified: 0 for [1,2,3,4,5] and 0 for [2,4], against the correct 9 and 4. On ascending input the while condition is never satisfied, so every bar is still on the stack when the loop ends and no area is computed. The sentinel forces the drain. Note [2,1,5,6,2,3] gives the right answer either way, because it happens to end on a descent -- which is exactly why this bug ships.
Both Largest Rectangle and Sliding Window Maximum have a `while` inside a `for`. Why are they still O(n)?

pch.quizShowAnswer

B — Each index is pushed exactly once and popped at most once, so total inner-loop work across the whole scan is bounded by n — Amortised analysis, the same shape as the two-stack queue's. Per-step cost is genuinely not constant -- one step can pop many entries -- but the total is linear because nothing is pushed twice. "The nesting makes it quadratic" is the standard misread, and the push-once-pop-once sentence is the answer to "prove it".
Why must the sliding-window deque hold indices rather than values?

pch.quizShowAnswer

B — Expiry is tested as dq[0] <= i - k, a question about position -- with raw values there is no way to know an entry has left the window — The descending input [9,8,7,6] shows it: nothing is ever dominated, so the deque shrinks only by expiry, and expiry is purely positional. Store values and the window constraint becomes unenforceable -- the maximum reported can come from outside the window entirely.
Median of Two Sorted Arrays: what is the correct complexity?

pch.quizShowAnswer

B — O(log min(n, m)) -- you binary-search the split point of the shorter array — The search space is the possible split positions of one array, and choosing the shorter one both tightens the bound and keeps the complementary index inside the longer array's range. Quoting O(log(n+m)) is close enough to sound right and is not what the algorithm does -- and the merge-based O(n+m) is the baseline you are being asked to beat.
Can a binary tree be reconstructed from its preorder traversal alone, without null markers?

pch.quizShowAnswer

B — No. The tree 1/(2, 3/(4,5)) and the left chain 1-2-3 both give "1,2,3" without markers; the markers are what make one pass sufficient — With markers the two serialise differently -- 1,2,#,#,3,4,#,#,5,#,# against 1,2,3,#,#,#,# -- and the round trip is verified to reproduce the exact shape. Without them you need preorder *plus* inorder (and distinct values) to disambiguate, which is two traversals instead of one.
Your LRU cache returns correct values on every get but fails a large test. Most likely cause?

pch.quizShowAnswer

B — `get` does not move the entry to the front, so a read is not counted as a use and eviction picks the wrong victim — A read is a use. Skip the reorder and every returned value is still correct -- the cache only diverges in *which* entry it discards, and only once evictions begin. That is why it passes small tests. Missing map cleanup on eviction is the other classic, and that one leaks memory rather than returning wrong values.
"Merge k sorted lists without a heap, in the same time bound." Possible?

pch.quizShowAnswer

B — Yes -- balanced divide-and-conquer pairwise merge is also O(N log k): log k rounds, each touching all N elements — Merge in pairs, then pairs of pairs, tournament style. The heap's genuine advantages are O(k) space rather than O(N) and that it handles streams of unknown length -- not the asymptotic bound. Sequential folding is the O(Nk) version, and concatenate-then-sort is O(N log N), a different bound.
Trapping Rain Water: why can the two-pointer version safely finalise the side with the smaller maximum?

pch.quizShowAnswer

B — The water above a column is capped by the smaller of the two bounding maxima, so that column's level is already known regardless of what lies further in — min(left_max, right_max) is the water level, so when left_max is the smaller one, no future discovery on the right can change it -- the answer for that column is settled and the pointer can advance. That argument is what removes the need for precomputed prefix maxima and drops the space from O(n) to O(1).

Recap

Every “hard” problem here is one or two known patterns wearing an unfamiliar costume: Trapping Rain Water is Two Pointers, Largest Rectangle is a Monotonic Stack, Merge k Sorted Lists is a min-heap.
Naming the pattern before coding turns a 45-minute struggle into a 15-minute implementation.
OrderedDict, heapq, and deque aren’t cheating — they’re the exact data structures the “from scratch” solutions are built to imitate.

You’ve now covered the full DSA with Python track: foundations, core data structures, sorting and searching, the interview patterns, dynamic programming, advanced graphs, competitive-programming topics, and two full problem sets. The best next step isn’t a new topic — it’s repetition. Pick a handful of problems from both sets, close the solutions, and solve them cold a second time next week. That’s what turns “I followed the solution” into “I recognized the pattern instantly.” Good luck out there.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading