cf.completefrontend
GREEDY & INTERVALS · ADVANCED

Huffman coding

Build the shortest possible prefix code for a text by repeatedly joining the two least frequent symbols into one group.

Time O(n²) with a sorted list, O(n log n) with a min-heapSpace O(n)3 practice problemsStep-through picture

The idea

Computers store each character as a pattern of bits (0s and 1s). A fixed code gives every character the same number of bits, but in real text some characters are much more common than others. Huffman coding gives common characters short codes and rare characters long codes, so the whole text takes fewer bits.

The codes must be prefix-free: no code is the start of another, so a reader always knows where one character ends. Such codes form a binary tree, where each character is a leaf and its code is the path from the root (left is 0, right is 1). A character's code length is its depth in the tree.

Huffman's greedy rule builds the best tree from the bottom up. Put every character in a list with its count. Repeatedly take the two smallest counts, join them under a new parent whose count is their sum, and put the parent back. When one item is left, the tree is done. Each join adds one bit to every character beneath it, so the total encoded length is the sum of all the joined counts.

An everyday example

Building a tournament bracket for lazy players

Players who rarely want to play are paired off first, in early rounds, so they end up deep in the bracket. Each round, the two least active groups merge into one team with their activity added together. Very active players join late and sit near the top, playing few rounds. Each round a player sits through costs them one bit, so putting busy players near the top keeps the total small.

How the example maps to the code
In the exampleIn the code
A player's activityA symbol's count in freqs
The two least active teamsfirst and second, the smallest two in queue
Merging them into one teamconst sum = first + second
Everyone in the team plays one more roundtotalBits += sum
Putting the new team back in linequeue.splice(pos, 0, sum)

From the slow way to huffman coding

  1. Start with a fixed code. With 5 different symbols you need 3 bits each, because 2 bits only give 4 patterns. A text of 23 symbols then takes 23 × 3 = 69 bits, whether a symbol appears 9 times or twice. Common symbols pay as much as rare ones.
  2. Shorter codes for common symbols would help, but codes of different lengths can be confused: if a is 0 and b is 01, the bits 01 could be b, or a followed by something else. The fix is a prefix-free code, where no code is the start of another. Such codes are exactly the leaves of a binary tree, and a symbol's code length is its depth.
  3. So the question becomes: which tree? Trying every tree shape with every way of placing the symbols would take far too long, because the number of trees grows faster than exponentially. But one fact is clear. The two rarest symbols should be the deepest leaves, and in a best tree the deepest leaves come in sibling pairs, so the two rarest symbols can be siblings.
  4. Join those two into one new item whose count is their sum. Every copy of either symbol now needs one more bit, which adds exactly sum bits. What's left is the same problem with one fewer item. Repeat: take the two smallest counts, join them, add sum to the total, and put the sum back. That loop is Huffman coding.

How it works

  1. Handle tiny inputs: no symbols means 0 bits; one symbol gets a 1-bit code, so it costs its count.
  2. Put all the counts in queue, sorted from smallest to largest.
  3. Take the two smallest counts, first and second, out of queue.
  4. Join them: sum = first + second. Every symbol under this new node gets one more bit, so add sum to totalBits.
  5. Put sum back into queue at its sorted position.
  6. Repeat until one item is left in queue. Return totalBits.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function huffmanTotalBits(freqs) {
  2. if (freqs.length === 0) return 0;
  3. if (freqs.length === 1) return freqs[0];
  4. const queue = [...freqs].sort((a, b) => a - b);
  5. let totalBits = 0;
  6. while (queue.length > 1) {
  7. const first = queue.shift();
  8. const second = queue.shift();
  9. const sum = first + second;
  10. totalBits += sum;
  11. let pos = 0;
  12. while (pos < queue.length && queue[pos] < sum) pos++;
  13. queue.splice(pos, 0, sum);
  14. }
  15. return totalBits;
  16. }

How fast it is

TimeO(n²) with a sorted list, O(n log n) with a min-heap
Extra memoryO(n)

There are n - 1 joins. Each one inserts into a sorted list, which can take O(n); with a heap each join takes O(log n). The queue holds at most n counts.

  • Best caseO(n log n)

    Counts that double, like [1, 1, 2, 4, 8, 16]: each sum ties the next count, so the pos scan stops at once and the sort is the main cost. Moving items in shift and splice is a fast memory copy in practice.

  • Average caseO(n^2)

    Random counts: each sum lands somewhere in the middle of queue, so the pos scan walks about half of it on each of the n - 1 joins.

  • Worst caseO(n^2)

    Counts that are close to each other, like [10, 11, 12, 13, 14, 15]: every sum is bigger than everything left, so the scan walks the whole queue each time.

Common mistakes

  • Adding up count * depth with depths taken from a tree built in the wrong order. Always join the two smallest counts currently in the queue, including counts made by earlier joins.
  • Forgetting the single-symbol case: the loop never runs and returns 0, but the text still needs one bit per character.
  • Asking for exact codes without fixing a tie-breaking rule. Different ties give different, equally good codes; compare total lengths instead.
  • Re-sorting the whole queue after every join, which costs O(n log n) per step. Insert in place or use a heap.

When to use it

Look for these clues in a problem:

  • The question is about compressing text or giving shorter codes to more common symbols.
  • It asks for the cheapest way to combine many piles, files, or ropes, where each join costs the size of the result.
  • Each step joins two items into one until a single item is left.
  • Joining the two smallest items first seems best, because early joins are paid for again and again later.

Check yourself

Answer each one in your head first, then open it.

Why does the single-symbol case return freqs[0] and not 0?

With one symbol the loop never runs, but each character still needs at least one bit to be written. So the total is one bit times the count.

Why does adding every sum give the total number of bits?

A symbol's code length is the number of joins above it. Each join adds one bit to every copy of every symbol inside it, and there are exactly sum such copies.

Can two different Huffman trees for the same counts have different totals?

No. Ties can lead to different trees and codes, but every one of them has the smallest possible total, so the totals are equal.

Why can't the codes 0, 01, and 11 be used together?

0 is the start of 01, so after reading 0 a reader can't tell whether the symbol is finished. A prefix-free code avoids this by putting every symbol on a leaf.

What does the code return for eight equal counts, [1, 1, 1, 1, 1, 1, 1, 1]?

24. Eight equal counts build a perfectly balanced tree in which every code is 3 bits long, so the total is 8 × 3.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The total cost of a tree is the sum of count × depth over all symbols. Each join puts one new level above both joined items, so it adds sum to that total, one bit for every copy of every symbol below it. That's why totalBits can be built one join at a time without drawing the tree.

The greedy choice is safe by an exchange argument. Take any best tree. Its deepest level holds two sibling leaves. If the two smallest counts aren't there, swap them in. Moving a smaller count deeper and a larger count up never raises the total: the change saves (big - small) × (deep - shallow) bits, which is zero or more. So some best tree has the two smallest counts as its deepest siblings.

Joining those two siblings into one item with count sum turns a tree for the old list into a tree for the new list whose cost is lower by exactly sum. So a best tree for the smaller list, plus this join, is a best tree for the original list. The loop applies this n - 1 times, one fewer item each time, and stops when only the root is left.

Going deeper

3 more ideas

Why the total equals the sum of the joins

A symbol's code length is its depth in the tree: the number of joins above it. Each join with count sum adds one bit to every copy of every symbol below it, and there are exactly sum such copies. So the total number of bits for the whole text, the sum of count * depth over all symbols, is the same as adding up sum for every join.

Why joining the two smallest first is safe

In a best tree, the two deepest leaves are siblings, and swapping the two smallest counts into those deepest spots never raises the total, because smaller counts lose least from deep placement. So some best tree joins the two smallest counts first. After joining them into one item, the problem is the same with one fewer item, and the same argument applies again.

Ties and speed

When counts tie, different choices can give different trees and different codes, but every Huffman tree has the same total length. That's why problems ask for the total bits rather than the exact codes. This template keeps queue sorted by inserting, which costs O(n²) in the worst case. A min-heap makes each step O(log n), for O(n log n) overall.

Work it by hand

Every step in a table, with why

Find the fewest bits for 5 symbols that appear 6, 2, 3, 3, and 9 times. Two of the symbols tie with a count of 3.

freqs = [6, 2, 3, 3, 9]

Stepqueue beforefirstsecondsumtotalBitsWhat happensWhy
1----0sort: [2, 3, 3, 6, 9]There is more than one symbol, so the loop is needed. The sorted copy puts the rarest counts first.
2[2, 3, 3, 6, 9]2355insert 5 at pos = 1The two rarest join. One 3 is taken now and the other waits; either choice gives the same total. queue becomes [3, 5, 6, 9].
3[3, 5, 6, 9]35813insert 8 at pos = 1The second 3 joins the item made in the last step. Joined items are treated like any other count. queue becomes [6, 8, 9].
4[6, 8, 9]681427insert 14 at pos = 1queue becomes [9, 14].
5[9, 14]9142350insert 23 at pos = 0The last join makes the root. Its count, 23, is the number of symbols in the whole text. queue is now [23].

It returns 50, because only one item is left in queue. A fixed 3-bit code needs 69. The code lengths are 1 bit for the 9, 2 bits for the 6, 3 bits for one 3, and 4 bits for the 2 and the other 3: 9 + 12 + 9 + 8 + 12 = 50.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Huffman codingO(n^2)O(n)The code as written, with a sorted list. It's fine for alphabets of a few hundred symbols.
Huffman with a min-heapO(n log n)O(n)Large alphabets, or whenever you want the standard speed.
Fixed-length codeO(n)O(1)Symbols are about equally common, or you need to jump to the k-th symbol without decoding everything before it.
Try every treeO(n!)O(n)Never. It only shows why a greedy rule is needed.

Extra memory: O(n): queue holds at most n counts. Building the actual codes would also need the tree, which has 2n - 1 nodes, still O(n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Huffman coding and the other approaches, on a scale where each line up is 10 times more steps.
  • Huffman coding O(n^2)
  • Huffman with a min-heap O(n log n)
  • Fixed-length code O(n)
  • Try every tree O(n!)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Huffman coding1001 million1 trillion
Huffman with a min-heap339,96620 million
Fixed-length code101,0001 million
Try every tree4 millionmore than a quadrillionmore than a quadrillion

Inputs that need care

6 tricky inputs
No symbols: freqs = []
The first line returns 0: an empty text needs no bits.
One symbol: freqs = [7]
It returns 7. The loop would never run, but each character still needs one bit to be written, so the code returns the count itself.
Two symbols: freqs = [4, 9]
One join with sum = 13, so it returns 13: each symbol gets a 1-bit code.
All counts equal: freqs = [5, 5, 5, 5]
The tree is perfectly balanced. The joins are 10, 10, and 20, for 40 bits, the same as a fixed 2-bit code.
A count of zero: freqs = [0, 3, 4]
The unused symbol still joins first and adds 3 bits for nothing, so it returns 10 instead of 7. Filter out zero counts before calling it.
Very uneven counts: freqs = [1, 1, 2, 4, 8, 16]
The tree becomes a long chain and the two rarest symbols get 5-bit codes, for 62 bits. That is still the best total, but code lengths can reach n - 1 bits, which matters if a file format limits them.

Variations and follow-ups

Twists interviewers add

Min-heap version

Replace the sorted list with a min-heap: pop the two smallest, push their sum. Each join then costs O(log n), so the whole build is O(n log n). JavaScript has no built-in heap, so you'd write a small one.

Two queues for sorted counts

If the counts are already sorted, keep them in one queue and put every new sum at the back of a second queue. The sums come out in increasing order by themselves, so the two smallest items are always at the fronts of the two queues. That builds the tree in O(n) after the sort.

Getting the actual codes

Keep tree nodes in the queue instead of plain numbers: a leaf has a symbol, and an inner node has left and right children. After building, walk the tree from the root, adding 0 for left and 1 for right, and record the path when you reach a leaf.

Joining ropes or files at the lowest cost

The same loop answers "join n ropes into one, where each join costs the combined length" and "merge sorted files, where each merge costs the total size". The total cost is the sum of all joins, exactly like totalBits.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "repeatedly combine the two smallest", "the lowest cost to join ropes or merge files", or "the shortest prefix-free code". All of these are Huffman with a different story.
  • Say the cost formula before the code: "each join of cost sum adds one level above every item inside it, so the total is the sum of all joins". It shows you know why totalBits += sum is right.
  • Mention the data structure: a sorted list is O(n^2), a min-heap is O(n log n). Most interviewers expect the heap and accept a short heap class or a clear note that you'd use one.
  • Test by hand: zero symbols, one symbol, and all equal counts. The common follow-up is "why not join the largest first?": joining large counts early pushes them deeper, so every copy of them pays extra bits.

Where frontend code uses it

The same idea in real UI code
  • Gzip and Brotli, which servers use to compress HTML, CSS, and JavaScript sent to the browser, both use Huffman codes as their final step.
  • PNG images are compressed with DEFLATE, which uses Huffman coding, and baseline JPEG images use Huffman coding too.
  • The cheapest way to concatenate many files or chunks, when each join costs the size of the result, follows the same smallest-two-first rule.

Related algorithms