The high-frequency patterns
By the end: You can recognise and solve the patterns that appear most often.
- Hash maps: the answer to a surprising number of questions
- Two pointers and sliding window
- Binary search, including on the answer
- Stacks and monotonic stacks
New to data structures & algorithms? Data structures are the standard ways of arranging data in memory, such as a list, a lookup table or a tree, and each makes some operations cheap and others expensive. Algorithms are the standard recipes for working through them. Big-O notation is the shorthand for how the cost grows as the data grows: a method that is fine on a hundred records can be unusable on a million, and this notation tells you which one you have before you find out in production. Why it matters
Interview problems are drawn from a surprisingly short list of shapes, and most of the difficulty is recognising which shape you have been handed. This section covers the four that appear most often, and for each one gives the phrase in the question that gives it away, a template short enough to write from memory, the cost, and the mistake that gets made under pressure. Learn the signals and a large share of problems stop being puzzles and become recall.
Phrase in the question Reach for
"how many", "count", "duplicate", "anagram" hash map
"pair that sums", "sorted array", "palindrome" two pointers
"substring", "subarray", "window", "longest" sliding window
"sorted", "minimum value that works", "k-th" binary search
"next greater", "previous smaller", "nesting" stack
"top k", "k largest", "stream" heapHash maps#
A hash map turns a scan into a lookup. Anything you would otherwise find by looking through the data again — has this appeared before, how many times, what else shares this property — costs one operation instead of a pass, which takes a quadratic solution down to linear.
The signal is any question about finding, counting, grouping or duplicates. The move that generalises is check before you insert: look for what you need, then add yourself, so you never match against yourself.
# Two sum: for each number, has its complement already been seen?
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
if target - n in seen: # check first
return [seen[target - n], i]
seen[n] = i # then insert
return []
# O(n) time, O(n) space. The brute force is two nested loops, O(n^2).Two standard library types cover most of the rest. Counter tallies in one line and answers most-common questions directly. defaultdict lets you group without checking whether the key exists yet, which removes the line most people forget.
from collections import Counter, defaultdict
Counter(words).most_common(3) # [('the', 12), ('a', 9), ('of', 7)]
# Group anagrams: the sorted letters are the identity of the group.
groups = defaultdict(list)
for word in words:
groups["".join(sorted(word))].append(word)
list(groups.values()) # [['eat','tea','ate'], ['tan','nat']]The dictionary key has to be hashable
A list cannot be a key and a tuple can, which is why grouping code converts one to the other. If you write groups[sorted(word)] it raises TypeError: unhashable type. Under time pressure this is the error people stare at longest, so recognise it on sight.
Two pointers#
Two indices walking through a sequence, usually inward from both ends. It works when the data is sorted or symmetric, because then the comparison at the current pair tells you which end to move: too small means raise the left, too large means lower the right. That decision is what removes the second loop.
The signal is a sorted array, a pair or triple that must satisfy something, or a question about reading from both directions.
def two_sum_sorted(nums, target):
"""The sorted version. No extra memory, unlike the hash map above."""
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1 # only the left end can raise the sum
else:
right -= 1 # only the right end can lower it
return []
# O(n) time, O(1) space. This is the template; most variants change the
# comparison, not the shape.The fast-and-slow variant uses the same two indices at different speeds instead of from opposite ends. It detects a cycle in a linked list, finds the middle in one pass, and removes the n-th node from the end without knowing the length.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity, not equality
return True
return FalseSliding window#
A contiguous range that grows at the right and shrinks at the left. Every element enters once and leaves once, so the whole scan is linear even though the window is re-examined constantly. The skill is knowing what to maintain as it moves, and shrinking exactly while the window is invalid rather than once.
The signal is the words subarray, substring, window, or longest and shortest applied to a contiguous run.
def longest_unique(s):
"""Longest substring with no repeated character."""
last_seen = {}
start = best = 0
for i, ch in enumerate(s):
# If we have seen it inside the current window, jump past it.
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = i
best = max(best, i - start + 1)
return best
longest_unique("abcabcbb") # 3, "abc"def min_window_sum(nums, target):
"""Shortest subarray summing to at least target. The while, not an if."""
start = total = 0
best = float("inf")
for end, n in enumerate(nums):
total += n
while total >= target: # shrink while valid, not once
best = min(best, end - start + 1)
total -= nums[start]
start += 1
return 0 if best == float("inf") else bestAn if where a while belongs
Shrinking with an if handles one element per step and silently returns a window that is too long. It passes the small examples and fails on the case where several elements must leave at once, which is usually the hidden test. If your window answer is slightly too big, this is why.
Binary search#
Halve the search space each step, which is why a million items take twenty comparisons. Writing it correctly under pressure is the hard part, so use one template and never improvise: keep the invariant that the answer is always inside the current range, and let the loop end when the range is empty.
def lower_bound(nums, target):
"""First index whose value is >= target. Returns len(nums) if none is."""
lo, hi = 0, len(nums) # hi is exclusive
while lo < hi: # ends when the range is empty
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1 # mid is ruled out
else:
hi = mid # mid might be the answer, so keep it
return loThe version that separates candidates is binary search on the answer, where you search a range of possible answers rather than an array. It applies whenever you can cheaply ask is this candidate good enough, and where good enough is monotonic — if a value works, every larger one works too.
def min_capacity(weights, days):
"""Smallest ship capacity that moves all packages within days trips."""
def fits(capacity):
used, load = 1, 0
for w in weights:
if load + w > capacity:
used, load = used + 1, 0
load += w
return used <= days
lo, hi = max(weights), sum(weights) # must fit the largest; one trip
while lo < hi:
mid = (lo + hi) // 2
if fits(mid):
hi = mid # this works, try smaller
else:
lo = mid + 1
return loWhere the infinite loop comes from
Mixing an inclusive hi with lo = mid, or writing while lo <= hi with hi = mid, leaves a range that stops shrinking and the loop never ends. Pick the exclusive-hi template above, and if you ever write lo = mid without the plus one, check it against a two-element input by hand.
Stacks#
A stack is the right structure whenever the most recent unfinished thing is what matters: matching brackets, nested structures, undo. The variant worth knowing by name is the monotonic stack, which keeps its contents sorted by discarding anything the new element makes irrelevant. That is what answers next greater element in one pass instead of two nested loops.
def next_greater(nums):
"""For each element, the next element to its right that is larger."""
answer = [-1] * len(nums)
stack = [] # indices, values decreasing
for i, n in enumerate(nums):
# Anything smaller than n has just found its answer.
while stack and nums[stack[-1]] < n:
answer[stack.pop()] = n
stack.append(i)
return answer
next_greater([2, 1, 2, 4, 3]) # [4, 2, 4, -1, -1]If you can explain why that inner while does not make it quadratic — each index enters and leaves exactly once — you have the amortised argument interviewers are listening for on this pattern.
Drilling this properly#
Doing many problems badly is how most people waste this. After each one, write a single line naming the pattern and the phrase in the question that signalled it, then close the solution. Before an interview reread only those lines. Recognition is the thing that transfers; the code is a template you already have.
Pattern Time Space Worth drilling
hash map O(n) O(n) two sum, group anagrams, top-k frequent
two pointers O(n) O(1) sorted pair, palindrome, remove duplicates
fast and slow O(n) O(1) cycle detection, middle node, n-th from end
sliding window O(n) O(k) longest unique, min window, max sum of size k
binary search O(log n) O(1) lower bound, rotated array, on the answer
monotonic stack O(n) O(n) next greater, daily temperatures, valid parensWhere people go wrong
Memorising solutions rather than patterns. A memorised solution fails the moment the question is phrased differently, which it always is. Learn the shape and why it works.
If this comes up in an interview
When do you reach for a hash map?
Whenever the question involves lookup, counting, grouping or duplicate detection. It turns a scan into a constant-time check, which is usually what converts a quadratic solution to a linear one.
How do you recognise a sliding window problem?
It asks about a contiguous subarray or substring with some property, usually the longest or shortest satisfying a condition. The shape is always expand with the loop, contract when the property breaks.
What is binary search on the answer?
When the answer is a value in a range and checking whether a candidate works is cheap, you binary search the range of possible answers rather than the input. The input does not need to be sorted; the answer space is.
What is a monotonic stack for?
Next-greater and next-smaller element questions in linear time. You keep the stack ordered, and when a new element breaks the order you have found the answer for everything it displaces.
Build this: Do 12 problems per pattern, and after each write one sentence naming the pattern and the signal that indicated it. Reread those sentences before an interview rather than the solutions.
Watch it explained
This is one section of Data structures & algorithms, 40 hours across 4 sections. Read it in full to get the whole topic in order.
Stop 44 of 50 on the AI Engineer route
0 of 50 topics done · 0h behind you, 603h to go
What you have marked done is stored in this browser only. It does not reach a server, and clearing site data will clear it.