8 drills · 8 pattern exercises · 19 micro drills
Patterns used in this topic, with difficulty breakdown.
Show how to add and remove elements from a min-heap, which always gives you the smallest element first.
All 8 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Show how to add and remove elements from a min-heap, which always gives you the smallest element first.
A heap is a complete binary tree stored in an array where each parent is smaller than its children — push and pop maintain this property in O(log n).
Prompt
Demonstrate pushing and popping elements from a min-heap using Python's heapq module.
Solution
import heapq
def heap_demo():
h = []
for val in [5, 3, 8, 1, 2]:
heapq.heappush(h, val) # O(log n) insert
# h is now a valid min-heap
result = []
while h:
result.append(heapq.heappop(h)) # O(log n) extract-min
return result
# Test: heap_demo() == [1, 2, 3, 5, 8]In plain English: Turn an unsorted list into a heap structure so the smallest element is always on top.
Bottom-up heapify sifts each non-leaf node down — this is O(n) because most nodes are near the bottom and barely need to move.
Prompt
Convert an arbitrary array into a min-heap in-place using heapq.heapify.
Solution
import heapq
def heapify_demo(a):
heapq.heapify(a) # O(n) in-place conversion
return a
# Test: a = [5, 3, 8, 1, 2]; heapify_demo(a); a[0] == 1
# Test: a = [9, 4, 7, 1, 3]; heapify_demo(a); a[0] == 1
def nsmallest_demo(a, k):
heapq.heapify(a)
return [heapq.heappop(a) for _ in range(k)]
# Test: nsmallest_demo([5,3,8,1,2], 3) == [1, 2, 3]In plain English: Find the k numbers that appear most often in an array.
Count frequencies with a hashmap, then use a min-heap of size k to track the top-k — pushing and popping keeps it efficient.
Prompt
Given an array of integers and k, return the k most frequent elements.
Solution
import heapq
from collections import Counter
def top_k_frequent(nums, k):
freq = Counter(nums)
# nlargest uses a min-heap of size k internally
return heapq.nlargest(k, freq.keys(), key=freq.get)
# Manual heap approach:
def top_k_frequent_manual(nums, k):
freq = Counter(nums)
heap = []
for num, cnt in freq.items():
heapq.heappush(heap, (cnt, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for cnt, num in heap]
# Test: top_k_frequent([1,1,1,2,2,3], 2) == [1, 2]In plain English: In a grid where rows and columns are sorted, find the kth smallest number without sorting everything.
Start from the top-left corner and use a min-heap to always expand the smallest unvisited cell — like BFS ordered by value.
Prompt
Given an n x n matrix where each row and column is sorted in ascending order, find the kth smallest element.
Solution
import heapq
def kth_smallest(matrix, k):
n = len(matrix)
# (value, row, col) — start with first element of each row
heap = [(matrix[i][0], i, 0) for i in range(min(n, k))]
heapq.heapify(heap)
val = 0
for _ in range(k):
val, r, c = heapq.heappop(heap)
if c + 1 < n:
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
return val
# Test: kth_smallest([[1,5,9],[10,11,13],[12,13,15]], 8) == 13In plain English: Figure out the maximum number of meetings happening at the same time, so you know how many rooms you need.
Sort by start time, use a min-heap of end times — if the earliest ending meeting ends before the new one starts, reuse that room; otherwise add a new room.
Prompt
Given a list of meeting time intervals [start, end], find the minimum number of conference rooms required.
Solution
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # sort by start time
rooms = [intervals[0][1]] # heap of end times
for start, end in intervals[1:]:
if start >= rooms[0]:
heapq.heappop(rooms) # reuse room: earliest ending <= new start
heapq.heappush(rooms, end)
return len(rooms)
# Test: min_meeting_rooms([[0,30],[5,10],[15,20]]) == 2
# Test: min_meeting_rooms([[7,10],[2,4]]) == 1In plain English: Combine k already-sorted lists into one single sorted list efficiently.
A min-heap of size k always holds the smallest unprocessed element from each array — pop the min and push the next from that array.
Prompt
Given k sorted arrays, merge them into one sorted array.
Solution
import heapq
def merge_k_sorted(arrays):
heap = []
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0)) # (val, array_idx, elem_idx)
result = []
while heap:
val, i, j = heapq.heappop(heap)
result.append(val)
if j + 1 < len(arrays[i]):
heapq.heappush(heap, (arrays[i][j + 1], i, j + 1))
return result
# Test: merge_k_sorted([[1,4,5],[1,3,4],[2,6]]) == [1,1,2,3,4,4,5,6]In plain English: Find the kth largest number in an unsorted array without fully sorting it.
Quick Select is partitioning (like quicksort) but only recursing into one half. Pick a pivot, partition around it, then check which partition the kth largest falls in. Average O(n), worst O(n^2).
Prompt
Given an integer array nums and an integer k, return the kth largest element. Solve in O(n) average time.
Solution
import random
def find_kth_largest(nums, k):
target = len(nums) - k # convert to kth smallest (0-indexed)
def quickselect(lo, hi):
# random pivot avoids worst-case O(n^2) on sorted/adversarial inputs
pivot_idx = random.randint(lo, hi)
nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
pivot = nums[hi]
store = lo # partition boundary: everything left of store is < pivot
for i in range(lo, hi):
if nums[i] < pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
if store == target:
return nums[store]
elif store < target:
return quickselect(store + 1, hi)
else:
return quickselect(lo, store - 1)
return quickselect(0, len(nums) - 1)
# Test: find_kth_largest([3,2,1,5,6,4], 2) == 5
# Test: find_kth_largest([3,2,3,1,2,4,5,5,6], 4) == 4In plain English: Schedule tasks so that identical tasks are at least n apart. Find the minimum total time including idle slots.
Greedily schedule the most frequent task first (max-heap). After executing a task, put it on cooldown. Use a queue to track when tasks become available again. Idle when no task is ready.
Prompt
Given a list of tasks (characters) and a cooldown period n, return the minimum number of intervals the CPU needs to finish all tasks. Same tasks must be separated by at least n intervals.
Solution
import heapq
from collections import Counter, deque
def least_interval(tasks, n):
counts = Counter(tasks)
heap = [-c for c in counts.values()] # max-heap (negate)
heapq.heapify(heap)
cooldown = deque() # (available_time, remaining_count)
time = 0
while heap or cooldown:
time += 1
if heap:
cnt = heapq.heappop(heap) + 1 # execute one (cnt is negative)
if cnt: # still has remaining executions
cooldown.append((time + n, cnt))
if cooldown and cooldown[0][0] == time:
heapq.heappush(heap, cooldown.popleft()[1])
return time
# Test: least_interval(["A","A","A","B","B","B"], 2) == 8
# A B _ A B _ A B
# Test: least_interval(["A","A","A","B","B","B"], 0) == 68 exercises: spot the signals, pick the method, avoid the trap.
Demonstrate pushing and popping elements from a min-heap.
Signals
heapq.heappush inserts in O(log n), heappop removes min in O(log n). Array-based complete binary tree.
Trap
Python's heapq is a min-heap. For max-heap, negate values or use a wrapper.
Convert an arbitrary array into a min-heap in-place.
Signals
heapq.heapify does bottom-up sift-down. O(n) because most nodes are near the bottom.
Trap
Inserting elements one by one is O(n log n). heapify is O(n) — know the difference.
Given an array of integers and k, return the k most frequent elements.
Signals
Count with Counter, then use min-heap of size k. Push all, pop when size > k. O(n log k).
Bucket sort by frequency: create buckets[freq] = [elements]. Scan from highest bucket. O(n).
Trap
Sorting all elements by frequency is O(n log n). Heap of size k is O(n log k) — better when k << n.
Given an n x n matrix where rows and columns are sorted, find the kth smallest element.
Signals
Min-heap with (value, row, col). Pop k times. Push right and down neighbors. O(k log n).
Binary search on value range [min, max]. Count elements <= mid. O(n log(max-min)).
Trap
Flattening and sorting is O(n² log n²). The heap approach exploits the sorted structure.
Given meeting intervals [start, end], find minimum conference rooms required.
Signals
Sort by start. Min-heap of end times. If earliest end <= new start, reuse room (pop). Else add room. O(n log n).
Separate start and end arrays, sweep-line counting overlaps. Same O(n log n), less intuitive.
Trap
The heap tracks the earliest-ending meeting. If it ends before the new one starts, the room is freed.
Given k sorted arrays, merge them into one sorted array.
Signals
Min-heap of size k: (value, array_idx, element_idx). Pop min, push next from same array. O(N log k).
Merge pairs of arrays recursively (like merge sort). O(N log k) same complexity.
Trap
Merging arrays one by one (array1 + array2, then + array3...) is O(N*k) — much worse.
Find the kth largest element in an unsorted array.
Signals
Min-heap of size k. Push each element; pop if heap > k. Top is kth largest. O(n log k).
Quickselect: partition and recurse on the relevant half. O(n) average.
Trap
A full sort is O(n log n). Quickselect is O(n) average but O(n²) worst case without randomization.
Given tasks with a cooldown period n between same tasks, find the minimum time to finish all tasks.
Signals
Formula: max(len(tasks), (max_freq - 1) * (n + 1) + count_of_max_freq). O(n).
Max-heap + cooldown queue. Simulate rounds. O(n * tasks) but elegant.
Trap
The formula handles the case when total tasks exceed the frame size. Don't forget to take max with len(tasks).
19 quick recall drills to reinforce this topic.
Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.
stack = []
stack.append(x)
stack.pop()Maintaining a parallel min stack gives O(1) getMin. Classic design problem.
self.stack.append(val)
self.min_stack.append(
min(val, self.min_stack[-1] if self.min_stack else val)
)heappush maintains the min-heap invariant. Used in merge-k-lists and streaming median.
import heapq
heapq.heappush(h, val)heapify converts a list to a heap in O(n). Faster than n individual pushes.
import heapq
heapq.heapify(a)heappop extracts the minimum. Pair with heappush for priority queue operations.
import heapq
heapq.heappop(h)Correct 2D init avoids the shared-row aliasing bug. Foundation for all grid DP.
grid = [[0]*cols for _ in range(rows)]nlargest uses a min-heap of size k internally. O(n log k) for top-k problems.
import heapq
top_k = heapq.nlargest(k, a)Character counting is the core technique for anagram detection and frequency-based problems.
from collections import Counter
freq = Counter(s)Counter gives instant frequency maps. Powers anagram checks and top-k problems.
from collections import Counter
freq = Counter(a)Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wTranspose + reverse-rows rotates 90 degrees clockwise in-place. Classic matrix manipulation.
n = len(m)
for i in range(n):
for j in range(i+1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
row.reverse()Iterative inorder (sorted order for BST). Count down k, return when k reaches 0. O(H + k) time.
def kthSmallest(root, k):
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0: return cur.val
cur = cur.rightHeap tracks room end times. If the earliest-ending room is free, reuse it; otherwise allocate a new one.
import heapq
intervals.sort()
rooms = [] # min-heap of end times
for start, end in intervals:
if rooms and rooms[0] <= start:
heapq.heappop(rooms) # reuse room
heapq.heappush(rooms, end)
return len(rooms)Custom key sorting is Python's primary sort mechanism. Foundation for interval and custom-order problems.
a.sort(key=lambda x: x[1])Merging sorted lists is the core of merge sort and merge-k-lists.
i = j = 0
merged = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
merged.append(a[i]); i += 1
else:
merged.append(b[j]); j += 1
merged.extend(a[i:])
merged.extend(b[j:])Lomuto partition is the core of quicksort and quickselect. Know it cold for kth-element problems.
def partition(a, lo, hi):
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return iPartition is the heart of quicksort. Same as Lomuto partition — drill until automatic.
def partition(a, lo, hi):
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return iGreedy formula: max count drives idle slots. Total time = max(n_tasks, (max_freq-1)*(n+1) + max_count).
freq = Counter(tasks)
mx = max(freq.values())
mx_cnt = sum(1 for v in freq.values() if v == mx)
return max(len(tasks), (mx - 1) * (n + 1) + mx_cnt)Deque gives O(1) operations at both ends. Essential for BFS and sliding window.
from collections import deque
q = deque()
q.append(x)
q.popleft()