Algorithms from zero
Toolbox: pattern recognition in code
Crux Read four code sketches, recognise which technique each implements (or should), and pick the right data structure or the highest-leverage fix.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyIn an interview or a code review you rarely get a labelled problem — you get a snippet and a constraint. The skill is reading the loop and naming the technique it implements, or spotting that the chosen structure is the wrong one. Read each sketch, then answer.
Goal
Practise the recognition half of the toolbox: given code, identify the pattern, judge whether the data structure fits the dominant operation, and choose the change that actually moves the complexity.
Snippet 1 — the nested loop on sorted data
def has_pair_with_sum(a, target): # a is sorted ascending
n = len(a)
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return True
return False Quiz
Completed
The input is sorted but this is O(n^2). What pattern does the sorted input call for, and what is the resulting complexity?
Heads-up There are no overlapping subproblems here — each pair is examined once. Memoisation caches repeated subresults, of which there are none. The fix is to exploit the sorted order with two pointers, not to cache.
Heads-up Pair-with-sum on sorted input is O(n) with two pointers, or O(n) average with a hash set on unsorted input. O(n^2) brute force ignores the strongest hint in the problem: the array is sorted.
Heads-up A heap gives you the extreme element, not pair relationships, and the data is already sorted so a heap adds nothing. The pattern the sortedness signals is the two-pointer sweep.
Snippet 2 — the recursion that recomputes
def ways(n, coins):
if n == 0: return 1
if n < 0 or not coins: return 0
# use coins[0] again, or drop it
return ways(n - coins[0], coins) + ways(n, coins[1:]) Quiz
Completed
This is correct but exponential on large n. What is the precise diagnosis and the standard fix?
Heads-up The base cases (n==0 returns 1, n<0 or empty returns 0) are correct and the recursion terminates. The cost is not a bug but the exponential reexploration of identical (remaining, index) states — that is the DP signal.
Heads-up Greedy counts at most one way, not all distinct ways, and can be wrong for non-canonical denominations. Counting combinations needs summing over subproblems, which is DP — greedy answers a different question.
Heads-up Two pointers solves relationship-on-sorted-sequence problems, not counting over a recursive choice space. The overlapping (remaining, index) states are the unmistakable cue for memoisation or tabulation.
Snippet 3 — the running k-th element
import heapq
def stream_kth_largest(stream, k):
h = [] # what kind of heap?
for x in stream:
heapq.heappush(h, x) # Python heapq is a MIN-heap
if len(h) > k:
heapq.heappop(h) # pops the smallest
return h[0] # the k-th largest seen so far Quiz
Completed
This keeps a running k-th largest with a size-k min-heap. Why is a MIN-heap (not a max-heap) the correct structure here?
Heads-up A max-heap puts the largest at the root, so evicting the right element (the smallest of your kept k) would cost an O(k) scan each time. The min-heap makes the eviction O(log k). Mirror logic gives a max-heap for the k smallest.
Heads-up The choice is forced by which element you must evict cheaply. Keeping the k largest means dropping the current smallest, so the smallest must be at the root — a min-heap. The orientation is not arbitrary.
Heads-up Maintaining a sorted list costs O(k) per insertion (shifting elements), giving O(n*k) overall, versus O(n log k) for the heap. For a streaming top-k the heap is the right structure precisely because insert and evict are both O(log k).
Snippet 4 — the unbounded window
def longest_unique_substring(s):
seen = set()
best = 0
for r in range(len(s)):
while s[r] in seen:
seen.add(s[r]) # BUG: should shrink from the left
seen.add(s[r])
best = max(best, len(seen))
return best Quiz
Completed
The intended technique is a sliding window over the string. The window never shrinks, so the loop is broken. What is the correct mechanism?
Heads-up Sorting destroys the substring (contiguous) structure the problem is about — a substring must be a contiguous slice of the original order. The sliding window with a left pointer preserves contiguity and runs in O(n).
Heads-up That is the O(n^2) brute force the window is designed to replace. The window's whole value is that the left pointer only moves forward, so total work is O(n) — never restart the inner scan.
Heads-up A heap surfaces the extreme by priority, which has nothing to do with maintaining a contiguous duplicate-free range. The pattern signalled by 'longest contiguous substring satisfying a condition' is the sliding window, not a heap.
Recap
Reading code for its pattern is the same flow run in reverse: a nested loop over sorted data should be two pointers (O(n)); a recursion that recomputes identical states is screaming for memoisation or tabulation (DP); a running k-th element forces a specific heap orientation by which element must be cheaply evicted; and ‘longest contiguous range satisfying a condition’ is a sliding window whose left pointer only moves forward. Name the pattern, check the data structure against the dominant operation, then change the one thing that moves the complexity.