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# TODO and
a passpass that will fail the sample asserts until you replace it. Hit Run
to check your output against the # expect# 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 heapqheapq 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 nn 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 <= 200001 <= n <= 200000 <= height[i] <= 1000000 <= 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 9def 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])) # 9def 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 ii is min(max_left, max_right) - height[i]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 nums1nums1 and nums2nums2 of sizes mm and
nn, return the median of the two arrays combined, in better than
time.
0 <= m, n <= 10000 <= m, n <= 1000,1 <= m + n <= 20001 <= 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.5def 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.5def 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 ii (the cut point in the
shorter array) fixes jj (the cut point in the longer array) automatically
— when left1 <= right2left1 <= right2 and left2 <= right1left2 <= 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) <= 1000001 <= 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 4def 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])) # 4def 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 ii is shorter than the bar at the top of the
stack, the taller bar can never extend any further right than i - 1i - 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_wordbegin_word, end_wordend_word, and a word_listword_list, return the
length of the shortest transformation sequence from begin_wordbegin_word to
end_wordend_word, changing one letter at a time, where every intermediate word
must exist in word_listword_list. Return 0 if no such sequence exists.
1 <= len(begin_word) <= 101 <= 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 0from 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)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_wordend_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 NN is the word count and
LL is the word length, Space .
5. Merge k Sorted Lists — LC 23 — Hard
Pattern: K-way Merge
Problem. You are given an array of kk linked lists, each sorted in
ascending order. Merge all the linked lists into one sorted linked list and
return it.
0 <= k <= 100000 <= k <= 10000, total nodes up to1000010000
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]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]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 NN nodes.
Complexity: Time where NN is the total node count and
kk 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
1000010000nodes, 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]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]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 NoneNone 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
capacitycapacity. Support get(key)get(key) in (returns the value, or -1 if
absent, and marks it as recently used) and put(key, value)put(key, value) in
(inserts or updates, evicting the least recently used entry if over
capacity).
1 <= capacity <= 30001 <= 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 4from 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)) # 4from 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: OrderedDictOrderedDict already tracks insertion order with
reordering (move_to_endmove_to_end) and removal from either end
(popitempopitem) — exactly the doubly linked list + hash map combo the
classic solution hand-rolls with a custom NodeNode class and prevprev/nextnext
pointers. Both give the same guarantees; OrderedDictOrderedDict just does the
pointer bookkeeping for you.
Complexity: Time for both getget and putput, Space .
8. Sliding Window Maximum — LC 239 — Hard
Pattern: Monotonic Stack (as a monotonic deque)
Problem. Given an array numsnums and a window size kk, return an array
of the maximum value in every contiguous window of size kk as it slides
from left to right.
1 <= k <= len(nums) <= 1000001 <= 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]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]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 .
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.
OrderedDictOrderedDict,heapqheapq, anddequedequearen’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.
If this helped you, consider buying me a coffee ☕
Buy me a coffeeWas this page helpful?
Let us know how we did