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) |
Here are three classic algorithms that do not fit neatly under any one earlier phase. Each one solves a specific, common problem well. Quickselect finds the Kth smallest or largest element without a full sort of anything. It is the Quick Sort from Sorting Intuition, minus the half of the work that Quick Sort does and Quickselect does not need. KMP (Knuth-Morris-Pratt) finds a pattern inside a larger text in O(n+m) time instead of the naive O(n×m), because it never checks characters again that 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. It is the classic real-world application of a heap, direct from Phase 5.
What ties them together is not a shared data structure. It is that each one takes an algorithm already built earlier in this curriculum and asks a sharper, narrower question of it: the partition of Quick Sort, but with a chase of only one answer instead of a full order; the pop-and-push cycle of a heap, but with a merge instead of only an extract.
Three techniques, no shared structure
# Quickselect reuses the partition() of Quick Sort from Sorting Intuition, unchanged. # KMP builds one small helper array (the "failure function") before the search. # 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) // the partition() of Sorting Intuition, unchanged
if pivotIndex == k:
return arr[pivotIndex]
elif pivotIndex < k:
// the answer is in the right piece only: the left piece is done, discard it
lo = pivotIndex + 1
else:
// the answer is in the left piece only: the right piece is done, discard it
hi = pivotIndex - 1KMP — build the failure function, then search — O(n+m)
function buildFailureFunction(pattern):
// lps[i] = the length of the longest prefix of pattern that is also a suffix ending at i
lps = array of zeros, length = pattern.length
length = 0 // the 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, do not restart at 0
else:
lps[i] = 0
i += 1
return lps
function kmpSearch(text, pattern):
lps = buildFailureFunction(pattern)
i, j = 0, 0 // i walks the text, j walks the pattern
while i < text.length:
if text[i] == pattern[j]:
i += 1
j += 1
if j == pattern.length:
return i - j // found: the start index of the match
elif j > 0:
// mismatch: skip ahead with what is 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
// the Phase 5 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 // the two least-frequent nodes...
right = pop minimum from minHeap
// ...merged into one, with the 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 root of the encoding treeQuickselect averages O(n): the same average-case reasoning as the partition of Quick Sort, but summed over a shrinking single side instead of two recursive halves. KMP is O(n+m): O(m) to build the failure function one time, and O(n) to scan the text one time. Each character of the text is visited a bounded number of times, thanks to the fallback (no restart from the start). Huffman Coding is O(n log n): there are n-1 merges, and each merge does 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) | This is the same pivot-choice risk as Quick Sort. A bad pivot (an already-sorted input, with a pick of the last element every time) shrinks the search space by only one element per step instead of about half. |
| KMP failure function (build) | O(m) | O(m) | This is one pass over the pattern. The fallback (length = lps[length - 1]) can move length backward, but it can do that only as many times in total as it moved forward. So the whole pass stays linear. |
| KMP search (scan) | O(n) | O(1) extra | i moves only forward through the text. j can fall back through lps, but it never makes i visit a character of the text that it already passed. |
| Huffman Coding (build the tree) | O(n log n) | O(n) | There are n-1 merges to collapse n leaf nodes into one tree. Each merge costs O(log n) for its two pops and one push. |
Quickselect degrading to O(n²) on a bad pivot
This is the identical failure mode as Quick Sort, for the identical reason. A predictably bad pivot choice puts zero elements on one side of every partition. This shrinks the remaining search space by exactly one element per step instead of about half. The fix is the same fix: pick a random pivot, or the median of a few sample elements, so an adversarial or already-sorted input cannot reliably trigger the worst case.
A subtly wrong failure function
This is genuinely one of the harder algorithms in the curriculum to get exactly right, and it is worth an honest warning, not false confidence. A failure function built even a little wrong usually does not crash. It quietly produces a table that makes kmpSearch skip past a real match or miss it. Trace buildFailureFunction() by hand on a small self-overlapping pattern (like "aabaaab") before you trust an implementation. The self-overlap is exactly what a broken failure function gets wrong first.
Huffman Coding with only one distinct character
The condition of the merge loop (while minHeap.size > 1) never runs, because the heap had only one element. The loop exits immediately, and buildHuffmanTree returns a single leaf node with no merges done. That leaf has no left or right children, so the usual "path from root to leaf" encoding does not work (a single node has no path at all). This degenerate case needs an explicit rule, handled outside the general algorithm. Usually, give that one character a 1-bit code (such as "0") by convention, instead of a try to force the tree-walk logic to produce one.
Ties in frequency resolved inconsistently
This does not break correctness. Every valid Huffman tree built from the same frequencies produces an optimal (minimum total encoded length) result, whichever same-frequency node the heap pops first on a tie. But it does mean that two runs, or two different heap implementations, can produce two different (and both valid) encodings for the identical input. This is worth naming explicitly, so a different-but-correct output on a re-run is not mistaken for a bug.
Sign in to mark problems done — progress syncs across devices.