Loading…

mediumGreedySometimes asked

Huffman Encoding

Greedy Algorithms · 14 of 23 · 12 min

You are given n symbols, each with a non-negative frequency (how often it appears). Construct a binary prefix code — a binary tree whose leaves are the symbols — that minimises the total number of encoded bits, where a symbol contributes frequency × (its depth in the tree) bits.

Return the **minimum total encoded length** (and/or the code assigned to each symbol). A prefix code means no symbol's codeword is a prefix of another's, which is guaranteed when every symbol is a leaf.

In plain English

Picture a binary tree whose leaves are the symbols. Walking from the root, each left/right edge appends a 0/1 bit, so a leaf's codeword is the path to it and its length is its depth. Because symbols are only at leaves, no codeword is a prefix of another — decoding is unambiguous. The total cost is Σ frequency × depth, and minimising it means keeping high-frequency symbols shallow. Greedily merging the two rarest nodes builds exactly that tree from the bottom up.

Examples

Example 1

Input: symbols = {a:5, b:9, c:12, d:13, e:16, f:45}
Output: 224
Note: Classic example. Merging the two smallest repeatedly gives f a 1-bit-ish shallow placement and a,b deep. Total bits Σ freq×depth = 224 (e.g. a=1100, b=1101, c=100, d=101, e=111, f=0).

Example 2

Input: freq = [4, 3, 2, 6]
Output: 29
Note: Merge 2+3=5, 4+5=9, 6+9=15 → total of merge sums 5+9+15 = 29. Same arithmetic as connecting ropes.

Example 3

Input: freq = [10]
Output: 10
Note: A single symbol gets a 1-bit code by convention → 10 × 1 = 10.

Constraints

1 ≤ n ≤ 10⁵ (number of distinct symbols)
0 ≤ frequency[i] ≤ 10⁹
Total encoded length can exceed 32 bits → accumulate in a long
For n = 1 the single symbol is conventionally given a code of length 1 (one bit)

Clarifying questions4First question: Why must symbols be at the leaves only?Explore questions

Q1.Why must symbols be at the leaves only?
To keep it a prefix code. If a symbol sat at an internal node, its codeword would be a prefix of every codeword below it, making decoding ambiguous. Leaves-only guarantees the prefix property.
Q2.Is the optimal tree unique?
Not necessarily — ties in frequency can be broken differently, and left/right is arbitrary. But the minimum total encoded length is unique.
Q3.What's the code length for a single symbol?
With one symbol there's no real tree; by convention it gets a 1-bit code, so the cost is its frequency × 1.
Q4.Can the total bit count overflow 32 bits?
With 10⁵ symbols at 10⁹ frequency and non-trivial depths, the sum easily exceeds int range. I accumulate it in a 64-bit long.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build an optimal prefix code by repeatedly merging the two LEAST frequent symbols into a parent whose frequency is their sum, using a min-heap. Each merge creates an internal tree node; after n−1 merges one root remains. A symbol's code length equals its depth in this tree, so rare symbols sit deep (long codes) and frequent symbols sit shallow (short codes). The total encoded bits = Σ frequency × depth, and this greedy provably minimises it. O(n log n) with a min-heap.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you build the tree bottom-up by always merging the two lowest-frequency nodes with a min-heap, understand that code length equals tree depth, and can argue why greedy yields a minimum-total-length prefix code.

Where candidates slip

Merging the two largest, forgetting to push the merged node back so it can be re-merged, or assigning codes to internal nodes instead of only leaves (breaking the prefix property).

How to stand out

State the exchange argument — the two least frequent symbols can be assumed to be the deepest siblings in some optimal tree, so merging them first is safe — and connect it to the optimal-binary-merge-tree family (connect ropes, file merging).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Repeated Two-Smallest Merge (Baseline)	`O(n²)`	`O(n)`	Open with this to fix the greedy idea — merge the two rarest symbols — and the 'code length = depth' insight before swapping the slow lookup for a heap.	Read
2	Min-Heap Tree Construction (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want. Phrase it as 'I only need the two smallest repeatedly, so a min-heap builds the tree in O(n log n)'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMinimise total bits of a prefix codeFrequencies fixed and known?No, streamingYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Repeated Two-Smallest Merge (Baseline)

TimeO(n²)SpaceO(n)

Open with this to fix the greedy idea — merge the two rarest symbols — and the 'code length = depth' insight before swapping the slow lookup for a heap.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A symbol's code length is its depth in the tree, so total bits = Σ frequency × depth. To shrink the total, which symbols should sit deepest (longest codes)?

2Hint 2Explore hint

The rarest ones. So build the tree bottom-up: repeatedly take the two lowest-frequency nodes and join them under a new parent whose frequency is their sum.

3Hint 3Explore hint

Without a heap: each round scan all live nodes for the two smallest frequencies, merge them, and add the new parent back. Repeat until one node remains; the answer is the sum of all merge frequencies.

A · Core idea

Treat each symbol as a leaf node carrying its frequency. Each round, find the two nodes with the lowest frequencies, create a parent whose frequency is their sum (with those two as children), and add the parent back to the pool. After n − 1 merges a single root remains; the minimum total encoded length is the sum of all the parent frequencies created along the way.

Why total bits equals Σ frequency × depth. Each left/right edge from the root adds one bit to a codeword, so a leaf at depth d has a d-bit code and contributes frequency × d bits. Equivalently, every time a node is buried under a new parent its frequency is counted one more time — which is exactly why summing the parent frequencies over all merges equals Σ frequency × depth. That dual view (sum of merge costs = weighted depth) is the same identity as connecting ropes.

Why merge the two rarest. You want long codes (deep leaves) for symbols that appear rarely, since their length is multiplied by a small frequency. Merging the two lowest-frequency nodes pushes them one level deeper and creates a combined node that, being small, will likely be merged again soon — keeping rare symbols sinking while frequent symbols stay near the root. That's the greedy that minimises the weighted depth.

Why prefix-correctness is automatic. Because symbols only ever become leaves (we merge nodes into a new parent, never attach a symbol mid-tree), no codeword is a prefix of another. The tree structure itself enforces the prefix property.

Why we don't ship this. Re-scanning all live nodes for the two minimums every round is O(n²). We only ever need the two smallest repeatedly, with one insertion after each merge — the textbook case for a min-heap, which the optimal approach uses.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

freq = [4, 3, 2, 6]

round 1

two smallest 2,3 → parent 5

Statepool=[4,6,5], total=5

Final result29

C · Code with teaching comments

Reference implementation previewpublic long huffmanCost(int[] freq) { if (freq.length == 1) { return freq[0]; // single symbol: 1-bit code by convention } List<Long> pool = new ArrayList<>();Explore the full code

solution.javaJava

Repeated Two-Smallest Merge (Baseline) — reference

4 teaching notes

1
public long huffmanCost(int[] freq) {
2
    // Edge case: one symbol still needs a 1-bit code by convention.
3
    if (freq.length == 1) {
4
        return freq[0]; // single symbol: 1-bit code by convention
5
    }
6
    List<Long> pool = new ArrayList<>();
7
    for (int f : freq) {
8
        pool.add((long) f);
9
    }
10
    long total = 0;
11
    while (pool.size() > 1) {
12
        // Scan for the lowest-frequency node — O(n).
13
        int i1 = minIndex(pool, -1);
14
        int i2 = minIndex(pool, i1);
15
        // Parent frequency = sum of the two rarest children.
16
        long sum = pool.get(i1) + pool.get(i2);
17
        // Adding every parent frequency yields Σ freq × depth, the total encoded bits.
18
        total += sum;
19
        pool.remove(Math.max(i1, i2));
20
        pool.remove(Math.min(i1, i2));
21
        pool.add(sum);
22
    }
23
    return total;
24
}
25
 
26
private int minIndex(List<Long> pool, int skip) {
27
    int best = -1;
28
    for (int i = 0; i < pool.size(); i++) {
29
        if (i == skip) {
30
            continue;
31
        }
32
        if (best == -1 || pool.get(i) < pool.get(best)) {
33
            best = i;
34
        }
35
    }
36
    return best;
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

The algorithm is one greedy rule — merge the two rarest — justified by 'code length = depth'. The O(n²) is purely the repeated scan for the two minimums; a min-heap finds them in O(log n) and is the only change needed.

ComplexityO(n²) time, O(n) space — Each round scans up to n live nodes for the two smallest → O(n) per round, with n−1 merges → O(n²). Storing nodes costs O(n) space.

E · Edge cases and pitfalls5single symbol — Handled separately: 1-bit code, cost = frequency.Explore edge cases

Edge cases handled

single symbolHandled separately: 1-bit code, cost = frequency.
two symbolsOne merge, both at depth 1 → total = freq[0] + freq[1].

Pitfalls

Merging the two LARGEST — gives rare symbols short codes, maximising total bits.
Assigning codes to internal nodes — breaks the prefix property.
Skipping this approach — verbalising 'merge the two rarest, code length = depth' is what the interviewer grades.

03.2

Approach 2 of 2 · Optimal

Min-Heap Tree Construction (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want. Phrase it as 'I only need the two smallest repeatedly, so a min-heap builds the tree in O(n log n)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need all nodes sorted — only the two smallest, repeatedly, with one push after each merge. Which structure gives min-removal and insertion in O(log n)?

2Hint 2Explore hint

Build a min-heap of nodes keyed by frequency. Pop the two smallest, make a parent with their summed frequency, push the parent back.

3Hint 3Explore hint

Repeat until one node (the root) remains. Accumulate each parent's frequency for the total bits; to emit codes, walk the tree assigning 0 going left and 1 going right.

A · Core idea

Put every symbol into a min-heap keyed by frequency. While more than one node remains, pop the two smallest, create a parent whose frequency is their sum (children = the two popped nodes), and push the parent back. The last remaining node is the root. The minimum total encoded length is the sum of all parent frequencies; the per-symbol codes come from a traversal that appends 0 on each left edge and 1 on each right edge.

Why a min-heap is the right structure. The baseline only ever needs: remove the smallest, remove the next smallest, insert the merged parent. A min-heap does each in O(log n), so the whole construction is O(n log n) — versus the baseline's O(n²) re-scan.

The exchange argument that proves optimality. Let the two least-frequent symbols be x and y. Claim: some optimal tree has x and y as sibling leaves at maximum depth. Take any optimal tree and let a and b be two deepest sibling leaves. Since x and y are the least frequent, swapping x with a and y with b never increases Σ freq × depth (moving a smaller frequency deeper and a larger one shallower can only help or tie). So there's an optimal tree where x and y are deepest siblings. Replacing that pair with a single merged leaf of frequency freq(x)+freq(y) reduces the problem to n − 1 symbols, and the cost differs by exactly freq(x)+freq(y) — the merge cost we add. Inductively, the greedy that merges the two smallest each step is optimal.

Why summing parent frequencies gives the answer. Each merge's parent frequency is counted again in every later merge it participates in — that compounding is precisely Σ freq × depth. Accumulating a.freq + b.freq on every merge captures the total encoded length without ever computing depths explicitly.

Why decoding is unambiguous. Symbols are only ever leaves, so no codeword prefixes another. A decoder walks the tree bit by bit from the root and emits a symbol exactly when it reaches a leaf.

Practical notes. Keep frequencies and the total in 64-bit (long in Java; Python ints are unbounded). Decide a deterministic tie-break (e.g. insertion order) if you need reproducible codes, since equal frequencies can yield different but equally optimal trees.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

freq = {a:5, b:9, c:12, d:13, e:16, f:45}

Interactive diagram

Huffman tree for the classic 6-symbol example

merge 5,9

Active call / nodeSupporting contextReturned stateNot active

Leaves are symbols; internal nodes hold summed frequencies. Depth = code length, so f (45) is shallow, a (5) and b (9) are deep. Total bits = 224.

Final result224

C · Code with teaching comments

solution.javaJava

Min-Heap Tree Construction (Optimal) — optimal

4 teaching notes

1
public long huffmanCost(int[] freq) {
2
    if (freq.length == 1) {
3
        return freq[0];
4
    }
5
    // Min-heap ordered by frequency — always hands back the two rarest nodes.
6
    PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(x.freq, y.freq));
7
    for (int f : freq) {
8
        heap.offer(new Node(f, null, null));
9
    }
10
    long total = 0;
11
    while (heap.size() > 1) {
12
        Node a = heap.poll();
13
        Node b = heap.poll();
14
        // New internal node; the two rarest become its children, sinking one level
15
        // deeper.
16
        Node parent = new Node(a.freq + b.freq, a, b);
17
        // Summed parent frequencies equal Σ freq × depth — the total encoded bits.
18
        total += parent.freq;
19
        heap.offer(parent);
20
    }
21
    // The lone remaining node is the root; traverse it to emit per-symbol codes.
22
    return total; // heap.peek() is the root of the code tree
23
}
24
 
25
private static class Node {
26
    long freq;
27
    Node left, right;
28
    Node(long freq, Node left, Node right) {
29
        this.freq = freq;
30
        this.left = left;
31
        this.right = right;
32
    }
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

This is the same optimal-binary-merge-tree engine as connecting ropes, but the tree is the deliverable: depths become code lengths. Whenever a baseline repeatedly needs 'the two smallest, then reinsert', a min-heap is the upgrade, and the exchange argument is the standard way to prove the greedy optimal.

ComplexityO(n log n) time, O(n) space — Heapify is O(n). There are n−1 merges; each does two pops and one push, all O(log n) → O(n log n). The heap and tree hold O(n) nodes → O(n) space.

E · Edge cases and pitfalls6single symbol — Returned early with a 1-bit code; no merges happen.Explore edge cases

Edge cases handled

single symbolReturned early with a 1-bit code; no merges happen.
all equal frequencies (power of 2 count)Builds a balanced tree; every code has the same length — Huffman ties fixed-length coding.
one dominant symbolThe frequent symbol stays near the root (short code); rare symbols sink deep — maximum compression benefit.

Pitfalls

Comparing node objects directly in Python's heapq without a tie-breaker — throws when frequencies tie.
Using a max-heap or merging the two largest — produces the worst, not best, total length.
Forgetting the n = 1 case — a lone symbol still needs a 1-bit code, not zero.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long huffmanCost(int[] freq) { if (freq.length == 1) { return freq[0]; } PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(x.freq, y.freq));Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Merging the two largest

Code length is depth, and you want rare symbols deep. Merging the largest first gives frequent symbols long codes and rare ones short codes — the maximum total length, exact opposite of the goal.

Explore the code comparison

Don't write this

PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(y.freq, x.freq)); // max-heap

Write this instead

PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(x.freq, y.freq)); // min-heap

Uncomparable nodes in Python heapq

Pushing (freq, node) tuples makes heapq compare node objects when two freqs tie, raising a TypeError. Add a unique increasing counter as a tie-breaker so comparison never reaches the payload.

Explore the code comparison

Don't write this

heapq.heappush(heap, (merged_freq, (a, b)))   # compares tuples → may compare a,b

Write this instead

heapq.heappush(heap, [merged_freq, counter, (a, b)])
counter += 1

32-bit overflow on total bits

With 10⁵ symbols at 10⁹ frequency and non-trivial depths, Σ freq × depth exceeds 2³¹ and an int total wraps negative.

Explore the code comparison

Don't write this

int total = 0;
// ...
total += parent.freq;

Write this instead

long total = 0;
// ...
total += parent.freq;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Min-heap: merge the two lowest-frequency nodes until one tree remains

Code pattern to memorize

heap = min-heap of leaf nodes (by frequency)
while heap size > 1:
    a = pop min
    b = pop min
    parent = node(freq = a.freq + b.freq, left = a, right = b)
    push parent
root = pop
# code length of a symbol = its depth; assign 0/1 down each edge

Rules to remember

1Always merge the two smallest-frequency nodes — the same two-smallest greedy as connecting ropes.
2The merged node's frequency is the sum of its children; push it back so it competes in future merges.
3It's a prefix code: every symbol is a leaf, so no code is a prefix of another and decoding is unambiguous.
4A symbol's code length = its depth in the tree, so total bits = Σ freq × depth — exactly the merge-cost sum.
5Multiple optimal trees can exist (ties break differently), but the total encoded length is unique.

Use this pattern when

Build a variable-length prefix code that minimises total encoded length
Compress data where symbol frequencies are known and skewed
Any 'merge two cheapest, cost = sum, minimise total' optimal-binary-merge-tree problem
You need an unambiguous code where no codeword prefixes another

Choose another pattern when

All symbols equally frequent → fixed-length codes are already optimal, Huffman gives no gain
You need codes of bounded maximum length → length-limited Huffman (package-merge), not plain greedy
Frequencies arrive as a stream / change over time → adaptive Huffman or arithmetic coding
You want the best possible ratio, not just prefix-optimal → arithmetic / range coding beats Huffman

Interview takeaway

Huffman is the canonical optimal prefix code: merge the two rarest symbols repeatedly so rare symbols end up deep (long codes) and common ones shallow (short codes). It's the same min-heap merge as 'connect ropes', and the exchange argument — the two lowest-frequency symbols can always be made deepest siblings — is what proves it optimal.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical optimal prefix code via the optimal-binary-merge-tree greedy. Recognise it whenever you minimise Σ frequency × depth (or any 'merge two cheapest, cost = sum, minimise total'): a min-heap merging the two smallest builds the tree in O(n log n). Same engine as connecting ropes; the exchange argument proves the two rarest can be deepest siblings.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Connect N Ropes with Minimum Cost
The same min-heap merge — ropes are symbol frequencies, the answer is the merge-cost sum.
Minimum Cost to Connect Sticks
Coming soon
Identical optimal-binary-merge-tree problem stated with sticks.
Length-Limited Huffman (Package-Merge)
Coming soon
Bound the maximum code length — plain greedy no longer works; use the package-merge algorithm.
Arithmetic / Adaptive Coding
Coming soon
When frequencies stream or you want better-than-prefix ratios, move beyond static Huffman.

Same pattern

←

Fractional Knapsack

Continue · Next problem

Minimum Number of Platforms

mediumGreedySometimes asked

Huffman Encoding

Greedy Algorithms · 14 of 23 · 12 min

In plain English

Examples

Example 1

Input: symbols = {a:5, b:9, c:12, d:13, e:16, f:45}
Output: 224
Note: Classic example. Merging the two smallest repeatedly gives f a 1-bit-ish shallow placement and a,b deep. Total bits Σ freq×depth = 224 (e.g. a=1100, b=1101, c=100, d=101, e=111, f=0).

Example 2

Input: freq = [4, 3, 2, 6]
Output: 29
Note: Merge 2+3=5, 4+5=9, 6+9=15 → total of merge sums 5+9+15 = 29. Same arithmetic as connecting ropes.

Example 3

Input: freq = [10]
Output: 10
Note: A single symbol gets a 1-bit code by convention → 10 × 1 = 10.

Constraints

1 ≤ n ≤ 10⁵ (number of distinct symbols)
0 ≤ frequency[i] ≤ 10⁹
Total encoded length can exceed 32 bits → accumulate in a long
For n = 1 the single symbol is conventionally given a code of length 1 (one bit)

Clarifying questions4First question: Why must symbols be at the leaves only?Explore questions

Q1.Why must symbols be at the leaves only?
To keep it a prefix code. If a symbol sat at an internal node, its codeword would be a prefix of every codeword below it, making decoding ambiguous. Leaves-only guarantees the prefix property.
Q2.Is the optimal tree unique?
Not necessarily — ties in frequency can be broken differently, and left/right is arbitrary. But the minimum total encoded length is unique.
Q3.What's the code length for a single symbol?
With one symbol there's no real tree; by convention it gets a 1-bit code, so the cost is its frequency × 1.
Q4.Can the total bit count overflow 32 bits?
With 10⁵ symbols at 10⁹ frequency and non-trivial depths, the sum easily exceeds int range. I accumulate it in a 64-bit long.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Merging the two largest, forgetting to push the merged node back so it can be re-merged, or assigning codes to internal nodes instead of only leaves (breaking the prefix property).

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Repeated Two-Smallest Merge (Baseline)	`O(n²)`	`O(n)`	Open with this to fix the greedy idea — merge the two rarest symbols — and the 'code length = depth' insight before swapping the slow lookup for a heap.	Read
2	Min-Heap Tree Construction (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want. Phrase it as 'I only need the two smallest repeatedly, so a min-heap builds the tree in O(n log n)'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Repeated Two-Smallest Merge (Baseline)

TimeO(n²)SpaceO(n)

Open with this to fix the greedy idea — merge the two rarest symbols — and the 'code length = depth' insight before swapping the slow lookup for a heap.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A symbol's code length is its depth in the tree, so total bits = Σ frequency × depth. To shrink the total, which symbols should sit deepest (longest codes)?

2Hint 2Explore hint

The rarest ones. So build the tree bottom-up: repeatedly take the two lowest-frequency nodes and join them under a new parent whose frequency is their sum.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

freq = [4, 3, 2, 6]

round 1

two smallest 2,3 → parent 5

Statepool=[4,6,5], total=5

Final result29

C · Code with teaching comments

solution.javaJava

Repeated Two-Smallest Merge (Baseline) — reference

4 teaching notes

1
public long huffmanCost(int[] freq) {
2
    // Edge case: one symbol still needs a 1-bit code by convention.
3
    if (freq.length == 1) {
4
        return freq[0]; // single symbol: 1-bit code by convention
5
    }
6
    List<Long> pool = new ArrayList<>();
7
    for (int f : freq) {
8
        pool.add((long) f);
9
    }
10
    long total = 0;
11
    while (pool.size() > 1) {
12
        // Scan for the lowest-frequency node — O(n).
13
        int i1 = minIndex(pool, -1);
14
        int i2 = minIndex(pool, i1);
15
        // Parent frequency = sum of the two rarest children.
16
        long sum = pool.get(i1) + pool.get(i2);
17
        // Adding every parent frequency yields Σ freq × depth, the total encoded bits.
18
        total += sum;
19
        pool.remove(Math.max(i1, i2));
20
        pool.remove(Math.min(i1, i2));
21
        pool.add(sum);
22
    }
23
    return total;
24
}
25
 
26
private int minIndex(List<Long> pool, int skip) {
27
    int best = -1;
28
    for (int i = 0; i < pool.size(); i++) {
29
        if (i == skip) {
30
            continue;
31
        }
32
        if (best == -1 || pool.get(i) < pool.get(best)) {
33
            best = i;
34
        }
35
    }
36
    return best;
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — Each round scans up to n live nodes for the two smallest → O(n) per round, with n−1 merges → O(n²). Storing nodes costs O(n) space.

E · Edge cases and pitfalls5single symbol — Handled separately: 1-bit code, cost = frequency.Explore edge cases

Edge cases handled

single symbolHandled separately: 1-bit code, cost = frequency.
two symbolsOne merge, both at depth 1 → total = freq[0] + freq[1].

Pitfalls

Merging the two LARGEST — gives rare symbols short codes, maximising total bits.
Assigning codes to internal nodes — breaks the prefix property.
Skipping this approach — verbalising 'merge the two rarest, code length = depth' is what the interviewer grades.

03.2

Approach 2 of 2 · Optimal

Min-Heap Tree Construction (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want. Phrase it as 'I only need the two smallest repeatedly, so a min-heap builds the tree in O(n log n)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You never need all nodes sorted — only the two smallest, repeatedly, with one push after each merge. Which structure gives min-removal and insertion in O(log n)?

2Hint 2Explore hint

Build a min-heap of nodes keyed by frequency. Pop the two smallest, make a parent with their summed frequency, push the parent back.

3Hint 3Explore hint

Repeat until one node (the root) remains. Accumulate each parent's frequency for the total bits; to emit codes, walk the tree assigning 0 going left and 1 going right.

A · Core idea

Why decoding is unambiguous. Symbols are only ever leaves, so no codeword prefixes another. A decoder walks the tree bit by bit from the root and emits a symbol exactly when it reaches a leaf.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

freq = {a:5, b:9, c:12, d:13, e:16, f:45}

Interactive diagram

Huffman tree for the classic 6-symbol example

merge 5,9

Active call / nodeSupporting contextReturned stateNot active

Leaves are symbols; internal nodes hold summed frequencies. Depth = code length, so f (45) is shallow, a (5) and b (9) are deep. Total bits = 224.

Final result224

C · Code with teaching comments

solution.javaJava

Min-Heap Tree Construction (Optimal) — optimal

4 teaching notes

1
public long huffmanCost(int[] freq) {
2
    if (freq.length == 1) {
3
        return freq[0];
4
    }
5
    // Min-heap ordered by frequency — always hands back the two rarest nodes.
6
    PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(x.freq, y.freq));
7
    for (int f : freq) {
8
        heap.offer(new Node(f, null, null));
9
    }
10
    long total = 0;
11
    while (heap.size() > 1) {
12
        Node a = heap.poll();
13
        Node b = heap.poll();
14
        // New internal node; the two rarest become its children, sinking one level
15
        // deeper.
16
        Node parent = new Node(a.freq + b.freq, a, b);
17
        // Summed parent frequencies equal Σ freq × depth — the total encoded bits.
18
        total += parent.freq;
19
        heap.offer(parent);
20
    }
21
    // The lone remaining node is the root; traverse it to emit per-symbol codes.
22
    return total; // heap.peek() is the root of the code tree
23
}
24
 
25
private static class Node {
26
    long freq;
27
    Node left, right;
28
    Node(long freq, Node left, Node right) {
29
        this.freq = freq;
30
        this.left = left;
31
        this.right = right;
32
    }
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Heapify is O(n). There are n−1 merges; each does two pops and one push, all O(log n) → O(n log n). The heap and tree hold O(n) nodes → O(n) space.

E · Edge cases and pitfalls6single symbol — Returned early with a 1-bit code; no merges happen.Explore edge cases

Edge cases handled

single symbolReturned early with a 1-bit code; no merges happen.
all equal frequencies (power of 2 count)Builds a balanced tree; every code has the same length — Huffman ties fixed-length coding.
one dominant symbolThe frequent symbol stays near the root (short code); rare symbols sink deep — maximum compression benefit.

Pitfalls

Comparing node objects directly in Python's heapq without a tie-breaker — throws when frequencies tie.
Using a max-heap or merging the two largest — produces the worst, not best, total length.
Forgetting the n = 1 case — a lone symbol still needs a 1-bit code, not zero.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Merging the two largest

Code length is depth, and you want rare symbols deep. Merging the largest first gives frequent symbols long codes and rare ones short codes — the maximum total length, exact opposite of the goal.

Explore the code comparison

Don't write this

PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(y.freq, x.freq)); // max-heap

Write this instead

PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(x.freq, y.freq)); // min-heap

Uncomparable nodes in Python heapq

Pushing (freq, node) tuples makes heapq compare node objects when two freqs tie, raising a TypeError. Add a unique increasing counter as a tie-breaker so comparison never reaches the payload.

Explore the code comparison

Don't write this

heapq.heappush(heap, (merged_freq, (a, b)))   # compares tuples → may compare a,b

Write this instead

heapq.heappush(heap, [merged_freq, counter, (a, b)])
counter += 1

32-bit overflow on total bits

With 10⁵ symbols at 10⁹ frequency and non-trivial depths, Σ freq × depth exceeds 2³¹ and an int total wraps negative.

Explore the code comparison

Don't write this

int total = 0;
// ...
total += parent.freq;

Write this instead

long total = 0;
// ...
total += parent.freq;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Min-heap: merge the two lowest-frequency nodes until one tree remains

Code pattern to memorize

heap = min-heap of leaf nodes (by frequency)
while heap size > 1:
    a = pop min
    b = pop min
    parent = node(freq = a.freq + b.freq, left = a, right = b)
    push parent
root = pop
# code length of a symbol = its depth; assign 0/1 down each edge

Rules to remember

1Always merge the two smallest-frequency nodes — the same two-smallest greedy as connecting ropes.
2The merged node's frequency is the sum of its children; push it back so it competes in future merges.
3It's a prefix code: every symbol is a leaf, so no code is a prefix of another and decoding is unambiguous.
4A symbol's code length = its depth in the tree, so total bits = Σ freq × depth — exactly the merge-cost sum.
5Multiple optimal trees can exist (ties break differently), but the total encoded length is unique.

Use this pattern when

Build a variable-length prefix code that minimises total encoded length
Compress data where symbol frequencies are known and skewed
Any 'merge two cheapest, cost = sum, minimise total' optimal-binary-merge-tree problem
You need an unambiguous code where no codeword prefixes another

Choose another pattern when

All symbols equally frequent → fixed-length codes are already optimal, Huffman gives no gain
You need codes of bounded maximum length → length-limited Huffman (package-merge), not plain greedy
Frequencies arrive as a stream / change over time → adaptive Huffman or arithmetic coding
You want the best possible ratio, not just prefix-optimal → arithmetic / range coding beats Huffman

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Connect N Ropes with Minimum Cost
The same min-heap merge — ropes are symbol frequencies, the answer is the merge-cost sum.
Minimum Cost to Connect Sticks
Coming soon
Identical optimal-binary-merge-tree problem stated with sticks.
Length-Limited Huffman (Package-Merge)
Coming soon
Bound the maximum code length — plain greedy no longer works; use the package-merge algorithm.
Arithmetic / Adaptive Coding
Coming soon
When frequencies stream or you want better-than-prefix ratios, move beyond static Huffman.

Same pattern

←

Fractional Knapsack

Continue · Next problem

Minimum Number of Platforms