Misc Algorithms
Quick reference
| Quickselect | O(n) average, O(n²) worst case |
| KMP failure function (build) | O(m) |
| KMP search (scan) | O(n) |
| Huffman Coding (build the tree) | O(n log n) |
Three classic algorithms that don't fit neatly under any one earlier phase, each solving one specific, common problem well. Quickselect finds the Kth smallest or largest element without fully sorting anything — it's Sorting Intuition's Quick Sort, minus the half of the work Quick Sort does that Quickselect doesn't need. KMP (Knuth-Morris-Pratt) finds a pattern inside a larger text in O(n+m) time instead of the naive O(n×m), by never re-checking characters it has already confirmed. Huffman Coding builds the most space-efficient variable-length binary encoding for a set of characters given how often each one appears — the classic real-world application of a heap, direct from Phase 5.
What ties them together isn't a shared data structure — it's that each one takes an algorithm already built earlier in this curriculum and asks a sharper, narrower question of it: Quick Sort's partition, but only chasing one answer instead of a full order; a heap's pop-and-push cycle, but merging instead of just extracting.
Three techniques, no shared structure
# Quickselect reuses Quick Sort's partition() from Sorting Intuition, unchanged. # KMP builds one small helper array (the "failure function") before searching. # Huffman Coding reuses the min-heap from Heaps & Priority Queue, keyed by frequency.
Quickselect — Kth smallest via one-sided partitioning — O(n) average
function quickSelect(arr, k): // find the element that belongs at index k once sorted
lo, hi = 0, arr.length - 1
while true:
pivotIndex = partition(arr, lo, hi) // Sorting Intuition's partition(), unchanged
if pivotIndex == k:
return arr[pivotIndex]
elif pivotIndex < k:
// answer is in the right piece only — left piece is done, discard it
lo = pivotIndex + 1
else:
// answer is in the left piece only — right piece is done, discard it
hi = pivotIndex - 1KMP — build the failure function, then search — O(n+m)
function buildFailureFunction(pattern):
// lps[i] = length of the longest prefix of pattern that's also a suffix ending at i
lps = array of zeros, length = pattern.length
length = 0 // length of the matched prefix so far
i = 1
while i < pattern.length:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1] // fall back to the next-best prefix — don't restart at 0
else:
lps[i] = 0
i += 1
return lps
function kmpSearch(text, pattern):
lps = buildFailureFunction(pattern)
i, j = 0, 0 // i walks text, j walks pattern
while i < text.length:
if text[i] == pattern[j]:
i += 1
j += 1
if j == pattern.length:
return i - j // found — starting index of the match
elif j > 0:
// mismatch: skip ahead using what's already matched — i never moves backward
j = lps[j - 1]
else:
i += 1
return -1 // pattern never foundHuffman Coding — repeatedly merge the two least-frequent nodes — O(n log n)
structure HuffmanNode:
char // the character, or NULL for a merged internal node
freq
left, right // -> another HuffmanNode, or NULL
function buildHuffmanTree(charFrequencies): // list of (char, freq) pairs
// Phase 5's heap, keyed by frequency instead of value
minHeap = a min-heap of HuffmanNode, ordered by freq
for (char, freq) in charFrequencies:
push HuffmanNode(char, freq, NULL, NULL) onto minHeap
while minHeap.size > 1:
left = pop minimum from minHeap // two least-frequent nodes...
right = pop minimum from minHeap
// ...merged into one, frequency summed
merged = HuffmanNode(NULL, left.freq + right.freq, left, right)
push merged onto minHeap
return pop minimum from minHeap // the one node left is the encoding tree's rootQuickselect averages O(n) — same average-case reasoning as Quick Sort's partition, but summed over a shrinking single side instead of two recursive halves. KMP is O(n+m): O(m) to build the failure function once, O(n) to scan the text once, each character of text visited a bounded number of times thanks to the fallback (never restarting from scratch). Huffman Coding is O(n log n): n-1 merges, each merge doing two pops and one push on a heap of up to n elements, and each of those heap operations costs O(log n).
| Operation | Time | Space | Why |
|---|---|---|---|
| Quickselect | O(n) average, O(n²) worst case | O(1) extra (in place) | Same pivot-choice risk as Quick Sort: a consistently bad pivot (already-sorted input, always picking the last element) shrinks the search space by only one element per step instead of roughly half. |
| KMP failure function (build) | O(m) | O(m) | One pass over the pattern; the fallback (length = lps[length - 1]) can move length backward, but it can only do that as many times total as it moved forward, keeping the whole pass linear. |
| KMP search (scan) | O(n) | O(1) extra | i only ever moves forward through text; j can fall back via lps but never causes i to re-visit a character of text it already passed. |
| Huffman Coding (build the tree) | O(n log n) | O(n) | n-1 merges to collapse n leaf nodes into one tree, each merge costing O(log n) for its two pops and one push. |
Quickselect degrading to O(n²) on a bad pivot
Identical failure mode to Quick Sort, for the identical reason: a predictably bad pivot choice puts zero elements on one side of every partition, shrinking the remaining search space by exactly one element per step instead of roughly half. The fix is the same fix too — pick a random pivot, or the median of a few sampled elements, so an adversarial or already-sorted input can't reliably trigger the worst case.
A subtly wrong failure function
This is genuinely one of the trickier algorithms in the curriculum to get exactly right, and it's worth an honest warning rather than false confidence: a failure function built even slightly wrong doesn't usually crash, it just quietly produces a table that causes kmpSearch to skip past a real match or miss it outright. Trace buildFailureFunction() by hand on a small self-overlapping pattern (like "aabaaab") before trusting an implementation — the self-overlap is exactly what a broken failure function gets wrong first.
Huffman Coding with only one distinct character
The merge loop's condition (while minHeap.size > 1) never runs, because the heap only ever had one element — the loop exits immediately and buildHuffmanTree returns a single leaf node with no merges performed. That leaf has no left/right children, so the usual 'path from root to leaf' encoding breaks down (a single node has no path at all). This degenerate case needs an explicit rule handled outside the general algorithm — commonly, assign that one character a 1-bit code (like "0") by convention, rather than trying to force the tree-walk logic to produce one.
Ties in frequency resolved inconsistently
This doesn't break correctness — every valid Huffman tree built from the same frequencies produces an optimal (minimum total encoded length) result, regardless of which same-frequency node the heap happens to pop first on a tie. But it does mean two runs, or two different heap implementations, can produce two different — and both entirely valid — encodings for the identical input. Worth naming explicitly so a different-but-correct output on a re-run doesn't get mistaken for a bug.
Sign in to mark problems done — progress syncs across devices.