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
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 <= 200000 <= height[i] <= 100000
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 9Show solution
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])) # 9Why 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 , Space .
2. Median of Two Sorted Arrays — LC 4 — Hard
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
time.
0 <= m, n <= 1000,1 <= m + n <= 2000
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.5Show solution
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.5Why 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 , Space .
3. Largest Rectangle in Histogram — LC 84 — Hard
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
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 4Show solution
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])) # 4Why 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 (each index is pushed and popped once), Space .
4. Word Ladder — LC 127 — Hard
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
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 0Show solution
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 where N is the word count and
L is the word length, Space .
5. Merge k Sorted Lists — LC 23 — Hard
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 to10000
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
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 where N is the total node count and
k is the number of lists, Space for the heap.
6. Serialize and Deserialize Binary Tree — LC 297 — Hard
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
10000nodes, node values in a signed 32-bit range.
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
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 for both serialize and deserialize, Space .
7. LRU Cache — LC 146 — Medium
Pattern: Linked Lists (doubly linked list + hash map)
Problem. Design a Least Recently Used (LRU) cache with a fixed
capacity. Support get(key) in (returns the value, or -1 if
absent, and marks it as recently used) and put(key, value) in
(inserts or updates, evicting the least recently used entry if over
capacity).
1 <= capacity <= 3000
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 4Show solution
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)) # 4Why it works: OrderedDict already tracks insertion order with
reordering (move_to_end) and 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 guarantees; OrderedDict just does the
pointer bookkeeping for you.
Complexity: Time for both get and put, Space .
8. Sliding Window Maximum — LC 239 — Hard
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
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
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 (each index pushed and popped at most once), Space .
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 | per-column | two-pointer | Water depends only on the smaller running maximum, so that side is already decided | |
| 2 | Median of Two Sorted Arrays | merge | Binary search the split point in the shorter array, not the value | ||
| 3 | Largest Rectangle in Histogram | A monotonic stack: each bar is pushed and popped once | |||
| 4 | Word Ladder | pairwise | Generate neighbours by mutation, never by comparing word pairs | ||
| 5 | Merge k Sorted Lists | sequential merge | Heap of k heads -- or balanced pairwise merge, same bound at space | ||
| 6 | Serialize / Deserialize | -- | each way | An explicit null marker is what makes the preorder string unambiguous | |
| 7 | LRU Cache | per op with a list | per op | Hash map for lookup + doubly linked list for eviction; neither alone does both | |
| 8 | Sliding Window Maximum | Monotonic deque of indices, so expiry is a position test |
Three bounds people misstate:
- Median of Two Sorted Arrays is , not . 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 amortised, with a
whileinside afor. Each element is pushed once and popped once. Reading the nesting as 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 . The heap's advantages are space instead of 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
Tab indents. Press Escape, then Tab, to leave the editor. Control plus Enter runs the code; Control plus Shift plus Enter submits it.
Press Run to see what your code prints.Drill 2 -- the deque holds indices, not values
Tab indents. Press Escape, then Tab, to leave the editor. Control plus Enter runs the code; Control plus Shift plus Enter submits it.
Press Run to see what your code prints.Drill 3 -- serialisation needs an explicit null marker
Tab indents. Press Escape, then Tab, to leave the editor. Control plus Enter runs the code; Control plus Shift plus Enter submits it.
Press Run to see what your code prints.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. , against for the prefix-array and monotonic-stack versions |
| "Why is not the right bound?" | Median of Two Sorted Arrays | You binary-search the split point of the shorter array, so it is . Always choosing the shorter one is both the tighter bound and what keeps the index arithmetic in range |
| "Prove the stack version is " | 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: rounds, each touching all N elements, so also . The heap's real edges are space instead of , 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 lookup but has no order; the list gives order and removal of a known node. Neither alone does both, and prev pointers are what make unlinking |
| "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.
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.
- 146LRU Cachemedium
- 4Median of Two Sorted Arrayshard
- 42Trapping Rain Waterhard
- 297Serialize and Deserialize Binary Treehard
- 84Largest Rectangle in Histogramhard
- 127Word Ladderhard
- 239Sliding Window Maximumhard
- 23Merge k Sorted Listshard
Self-check
Largest Rectangle in Histogram, without the trailing 0 sentinel. What does it return for [1, 2, 3, 4, 5]?
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.
Show answer
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)?
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".
Show answer
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?
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.
Show answer
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?
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.
Show answer
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?
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.
Show answer
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?
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.
Show answer
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?
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.
Show answer
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?
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).
Show answer
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, anddequearen'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.