5 drills · 5 pattern exercises · 12 micro drills
Patterns used in this topic, with difficulty breakdown.
Sort a list by repeatedly picking the next element and inserting it into its correct spot.
All 5 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Sort a list by repeatedly picking the next element and inserting it into its correct spot.
Builds the sorted portion one element at a time by shifting — efficient for nearly-sorted data because few shifts are needed.
Prompt
Sort an array using insertion sort.
Solution
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # shift larger elements right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
# Test: insertion_sort([5,3,1,4,2]) == [1,2,3,4,5]In plain English: Sort a list by splitting it in half, sorting each half, and merging them back together.
Divide and conquer: splitting halves the problem, merging combines sorted halves in linear time — guaranteed O(n log n).
Prompt
Sort an array using merge sort.
Solution
def merge_sort(a):
if len(a) <= 1:
return a
m = len(a) // 2 # divide at midpoint
L = merge_sort(a[:m])
R = merge_sort(a[m:])
res, i, j = [], 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
res.append(L[i]); i += 1
else:
res.append(R[j]); j += 1
res.extend(L[i:])
res.extend(R[j:])
return res
# Test: merge_sort([38,27,43,3,9,82,10]) == [3,9,10,27,38,43,82]In plain English: Sort a list by picking a pivot, putting smaller elements left and larger right, then recursing.
Partitioning places the pivot in its final sorted position — everything left is smaller, everything right is larger.
Prompt
Sort an array using quicksort with Lomuto partition.
Solution
def quicksort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p = partition(a, lo, hi)
quicksort(a, lo, p - 1)
quicksort(a, p + 1, hi)
return a
def partition(a, lo, hi):
pivot = a[hi]
i = lo # i tracks boundary of <= pivot
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 i
# Test: quicksort([10,7,8,9,1,5]) == [1,5,7,8,9,10]In plain English: Combine two sorted arrays into one — the merge step that powers merge sort.
The merge step is the workhorse of merge sort — two pointers always pick the smaller remaining element.
Prompt
Merge two sorted arrays into one sorted array. (Speed drill — same as #6.)
Solution
def merge(a, b):
res, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
res.append(a[i]); i += 1
else:
res.append(b[j]); j += 1
res.extend(a[i:])
res.extend(b[j:])
return res
# Test: merge([1,3,5,7], [2,4,6,8]) == [1,2,3,4,5,6,7,8]In plain English: Sort an array containing only 0s, 1s, and 2s in a single pass.
Three pointers carve the array into four regions: 0s, 1s, unknown, and 2s — each swap shrinks the unknown region.
Prompt
Sort an array of 0s, 1s, and 2s in one pass.
Solution
def dutch_flag(a):
lo, mid, hi = 0, 0, len(a) - 1
# 0: swap to lo, 2: swap to hi, 1: skip
while mid <= hi:
if a[mid] == 0:
a[lo], a[mid] = a[mid], a[lo]
lo += 1; mid += 1
elif a[mid] == 1:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1
return a
# Test: dutch_flag([2,0,1,2,1,0]) == [0,0,1,1,2,2]5 exercises: spot the signals, pick the method, avoid the trap.
Sort an array using insertion sort.
Signals
For each element, shift larger elements right and insert. O(n²) worst case, O(n) best (nearly sorted).
Trap
This is an algorithm implementation drill, not a problem-solving drill. Know the invariant: left portion is always sorted.
Sort an array using merge sort.
Signals
Split array in half, recursively sort, merge sorted halves. O(n log n) time, O(n) space.
Trap
The merge step is where the work happens — two pointers picking the smaller element from each sorted half.
Sort an array using quicksort with Lomuto partition.
Signals
Partition places pivot correctly. Recurse on left and right partitions. O(n log n) average.
Trap
Worst case is O(n²) with bad pivot choice (already sorted). Random pivot selection avoids this.
Merge two sorted arrays into one sorted array.
Signals
One pointer per array, always pick the smaller front element. O(n+m).
Trap
Concatenate + re-sort is O((n+m) log(n+m)). Merge is O(n+m) — exploit the sorted property.
Sort an array of 0s, 1s, and 2s in one pass.
Signals
lo/mid/hi pointers. Swap 0s to lo, 2s to hi, skip 1s. One pass, O(n) time, O(1) space.
Counting sort (count 0s, 1s, 2s, overwrite) also O(n) but requires two passes.
Trap
General sorting is O(n log n). This is a special case with only 3 values → can do O(n).
12 quick recall drills to reinforce this topic.
Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-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 wCustom 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:])Sort-then-merge is the standard O(n log n) approach to interval union.
a.sort()
res = [a[0]]
for s, e in a[1:]:
if s <= res[-1][1]:
res[-1][1] = max(res[-1][1], e)
else:
res.append([s, e])Spiral traversal uses shrinking boundaries: top, bottom, left, right.
res = []
t, b, l, r = 0, len(m)-1, 0, len(m[0])-1
while t <= b and l <= r:
for c in range(l, r+1): res.append(m[t][c])
t += 1
for c in range(t, b+1): res.append(m[c][r])
r -= 1Lomuto 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 iConverging pointers shrink the search space from both ends. Core of two-sum-sorted and palindrome.
l, r = 0, len(a) - 1
while l < r:
# process a[l], a[r]
l += 1; r -= 1Three-way partition handles duplicates efficiently. Classic for sort-colors type problems.
lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
if a[mid] < pivot:
a[lo], a[mid] = a[mid], a[lo]
lo += 1; mid += 1
elif a[mid] == pivot:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1Move toward the higher neighbor — a peak must exist on that side. Uses lo < hi (not <=) and hi = mid (not mid-1).
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < a[mid + 1]:
lo = mid + 1
else:
hi = mid
return loThe standard binary search template. Foundation for all logarithmic search problems.
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target: return mid
elif a[mid] < target: lo = mid + 1
else: hi = mid - 1