SyntaxPilot
Courses/DSA and Coding Problems/Lesson 61
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 61 of 90

Huffman coding and minimum cost to connect ropes

queued

These are the notes for DSA episode 61. A cable crew joins pieces of cable two at a time, and every join costs the total length of the two pieces. In which order should they join them? Trying every pair at every step is correct but Time Limit Exceeded on just 12 pieces. A tempting greedy rule (sort once, then join left to right) gives 39 where 36 is possible. The insight: every piece is paid once for every join above it, so always join the two smallest pieces right now, which a min-heap gives in O(log n). The very same rule builds Huffman codes, the idea inside zip files: abracadabra needs 23 bits instead of 88. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

A repair crew has leftover cable pieces of different lengths. They join two pieces at a time into one longer piece, until a single piece is left. The joining machine charges by length: joining 3 m and 5 m costs 8. The order matters.

On site In code
A cable piece of length x an int in sticks
Join two pieces remove two values, add their sum
Cost of a join a + b
The two shortest pieces right now poll() twice from a min-heap

Every word, from zero

  • Greedy: take the best-looking choice now and never undo it (episodes 59-60); it needs a proof.
  • Heap / priority queue: a structure that always hands out the smallest item (min-heap) in O(log n); Java's PriorityQueue is a min-heap by default (episode 43).
  • poll() / add(): remove the smallest / insert, each O(log n).
  • Exchange argument: swap the greedy choice into any optimal answer and show it stays optimal.
  • Binary tree, leaf, depth: every join makes a parent of two pieces; original pieces are leaves; depth = number of joins above a leaf.
  • Integer overflow: an int holds up to 2,147,483,647 (about 214 crore); past that it wraps to negative. long holds about 9.2 × 10^18.
  • Bit, ASCII: a bit is 0 or 1; ASCII stores each character in 8 bits.
  • Prefix-free code: no code is the start of another, so bits decode without separators.
  • Huffman coding: the optimal prefix-free code, built by always merging the two rarest symbols (David Huffman, 1952).
  • record: a short Java class for plain data (Java 16+): record Node(int freq, char ch, Node left, Node right) {}.

Problem statement

LeetCode 1167, Minimum Cost to Connect Sticks. Given lengths sticks, join any two sticks x and y at cost x + y until one stick remains. Return the minimum total cost.

sticks Answer
[2, 4, 3] 14 (2+3 = 5, then 5+4 = 9; 5 + 9)
[1, 8, 3, 5] 30
[5] 0

Constraints: 1 ≤ sticks.length ≤ 10^4, 1 ≤ sticks[i] ≤ 10^4.

Obvious idea: try every pair at every step

import java.util.*;

public class Main {
    static int connectSticks(int[] sticks) {
        List<Integer> s = new ArrayList<>();
        for (int x : sticks) s.add(x);
        return best(s);
    }
    static int best(List<Integer> s) {
        if (s.size() <= 1) return 0;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < s.size(); i++)
            for (int j = i + 1; j < s.size(); j++) {
                List<Integer> next = new ArrayList<>();
                for (int k = 0; k < s.size(); k++)
                    if (k != i && k != j) next.add(s.get(k));
                int joined = s.get(i) + s.get(j);
                next.add(joined);
                res = Math.min(res, joined + best(next));
            }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(connectSticks(new int[]{2, 4, 3}));
        System.out.println(connectSticks(new int[]{1, 8, 3, 5}));
    }
}
14
30

On 12 random pieces: Time Limit Exceeded. There are 66 pairs to try first, then 55, then 45, …: about 9 × 10^12 orders.

A greedy trap: sort once, join left to right

import java.util.*;

public class Main {
    static int connectSticks(int[] sticks) {
        int[] s = sticks.clone();
        Arrays.sort(s);
        int cost = 0, have = s[0];
        for (int i = 1; i < s.length; i++) {
            have += s[i];
            cost += have;
        }
        return cost;
    }
    public static void main(String[] args) {
        System.out.println(connectSticks(new int[]{2, 4, 3}));
        System.out.println(connectSticks(new int[]{1, 8, 3, 5}));
        System.out.println(connectSticks(new int[]{4, 4, 5, 5}));
    }
}
14
30
39

[4, 4, 5, 5]: joining 4 + 4, then 5 + 5, then 8 + 10 costs 8 + 10 + 18 = 36. The growing cable stops being one of the smallest pieces after the first join, and we keep paying for it.

The key insight: always join the two smallest NOW

  • Draw the joins as a tree. A piece is paid once for every join above it (its depth). In [1, 8, 3, 5] → 1+3=4, 4+5=9, 9+8=17, the 1 is inside the 4, the 9 and the 17: paid 3 times.
  • So short pieces should be deep and long pieces near the top.
  • Rule: join the two smallest pieces currently available (joined pieces count), put the result back, repeat.
  • Why it's safe (exchange argument): in any optimal tree, the deepest pair are siblings. Swap the two smallest pieces into that deepest pair: they're paid the most times and are the smallest, so the total can't go up.

Solution in Java: a min-heap

import java.util.*;

public class Main {
    static long connectSticks(int[] sticks) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        for (int s : sticks) heap.add((long) s);
        long cost = 0;
        while (heap.size() > 1) {
            long a = heap.poll(), b = heap.poll();
            cost += a + b;
            heap.add(a + b);
        }
        return cost;
    }
    public static void main(String[] args) {
        System.out.println(connectSticks(new int[]{2, 4, 3}));
        System.out.println(connectSticks(new int[]{1, 8, 3, 5}));
        System.out.println(connectSticks(new int[]{4, 4, 5, 5}));
        System.out.println(connectSticks(new int[]{5}));
    }
}
14
30
36
0

The 12 pieces that timed out: 2008 metres, 0 ms. One lakh pieces (each 1 to 10,000): 100000 pieces: 8171371511 metres, 67 ms (times vary). That total, about 817 crore, does not fit in an int.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

// Minimum Cost to Connect Sticks (LeetCode 1167): always join the two smallest (min-heap).
long long connectSticks(const vector<int>& sticks) {
    priority_queue<long long, vector<long long>, greater<long long>> heap(sticks.begin(), sticks.end());
    long long cost = 0;
    while (heap.size() > 1) {
        long long a = heap.top(); heap.pop();
        long long b = heap.top(); heap.pop();
        cost += a + b;
        heap.push(a + b);
    }
    return cost;
}

int main() {
    cout << connectSticks({2, 4, 3}) << "\n";
    cout << connectSticks({1, 8, 3, 5}) << "\n";
    cout << connectSticks({4, 4, 5, 5}) << "\n";
    cout << connectSticks({5}) << "\n";
}
14
30
36
0

(std::priority_queue is a max-heap by default; greater<> makes it a min-heap.)

The same solution in Python

import heapq

# Minimum Cost to Connect Sticks (LeetCode 1167): heapq is a min-heap.
def connect_sticks(sticks):
    heap = list(sticks)
    heapq.heapify(heap)
    cost = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        cost += a + b
        heapq.heappush(heap, a + b)
    return cost

print(connect_sticks([2, 4, 3]))
print(connect_sticks([1, 8, 3, 5]))
print(connect_sticks([4, 4, 5, 5]))
print(connect_sticks([5]))
14
30
36
0

Huffman coding: the same rule compresses text

  • ASCII spends 8 bits per letter. Morse code's trick: common letters get short codes (E is one dot).
  • Put the codes in a binary tree: left = 0, right = 1, letters at the leaves. That makes the code prefix-free.
  • A letter's code length is its depth, and it's paid once per occurrence. Total bits = Σ count × depth: exactly the cable cost with counts as lengths. So: always merge the two rarest.

By hand on abracadabra (a 5, b 2, r 2, c 1, d 1): merge c+d = 2; then two of the three 2s (r and the pair) = 4; then b + 4 = 6; then a + 6 = 11 (the root). Codes: a = 0 (1 bit), b = 10, r = 110, c = 1110, d = 1111. Bits: 5·1 + 2·2 + 2·3 + 1·4 + 1·4 = 23.

import java.util.*;

public class Main {
    record Node(int freq, char ch, Node left, Node right) {}
    static Map<Character, String> codes = new TreeMap<>();
    static void walk(Node n, String code) {
        if (n.left() == null) { codes.put(n.ch(), code.isEmpty() ? "0" : code); return; }
        walk(n.left(), code + "0");
        walk(n.right(), code + "1");
    }
    static void huffman(String text) {
        Map<Character, Integer> freq = new TreeMap<>();
        for (char c : text.toCharArray()) freq.merge(c, 1, Integer::sum);
        PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> x.freq() - y.freq());
        for (var e : freq.entrySet()) heap.add(new Node(e.getValue(), e.getKey(), null, null));
        while (heap.size() > 1) {
            Node a = heap.poll(), b = heap.poll();
            heap.add(new Node(a.freq() + b.freq(), '*', a, b));
        }
        codes.clear();
        walk(heap.poll(), "");
        int bits = 0;
        for (char c : text.toCharArray()) bits += codes.get(c).length();
        System.out.println(freq + " " + codes);
        System.out.println(text.length() * 8 + " bits as ASCII, " + bits + " bits as Huffman");
    }
    public static void main(String[] args) {
        huffman("abracadabra");
    }
}
{a=5, b=2, c=1, d=1, r=2} {a=0, b=10, c=1110, d=1111, r=110}
88 bits as ASCII, 23 bits as Huffman

With ties (several counts of 2) different trees are possible; they all give the same minimum total (23).

Huffman in Python

import heapq
from collections import Counter

# Huffman codes: heap of (count, tie-breaker, tree); merge the two rarest.
def huffman(text):
    heap = [(n, i, ch) for i, (ch, n) in enumerate(sorted(Counter(text).items()))]
    heapq.heapify(heap)
    k = len(heap)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        heapq.heappush(heap, (a[0] + b[0], k, (a[2], b[2])))
        k += 1
    codes = {}
    def walk(t, code):
        if isinstance(t, str):
            codes[t] = code or "0"
        else:
            walk(t[0], code + "0")
            walk(t[1], code + "1")
    walk(heap[0][2], "")
    return codes, sum(len(codes[c]) for c in text)

codes, bits = huffman("abracadabra")
print(dict(sorted(codes.items())), bits, "bits")
{'a': '0', 'b': '110', 'c': '100', 'd': '101', 'r': '111'} 23 bits

(Python broke the ties differently, so b, c, d, r all got 3 bits; the total is still 23.)

Three real bugs

Bug 1: a max-heap

new PriorityQueue<>(Collections.reverseOrder()):

16
46

16 instead of 14 and 46 instead of 30: the longest pieces end up deepest and are paid again and again.

Bug 2: not putting the joined piece back

Without heap.add(a + b);:

5
17

The joined pieces vanish; we only pay for pairs of original pieces and never make one cable.

Bug 3: everything in int

On one lakh pieces:

100000 pieces: -418563081 metres, 79 ms

The real total (8,171,371,511) is past Integer.MAX_VALUE (2,147,483,647), so the int wrapped to negative. Use long.

Complexity

Approach Time Space Big input
Every pair at every step ≈ (n!)² / 2ⁿ O(n²) lists 12 pieces: Time Limit Exceeded
Sort once, join in order O(n log n) O(n) wrong (39 instead of 36)
Min-heap O(n log n) O(n) 1 lakh pieces: 67 ms
Huffman (k distinct letters, text length m) O(m + k log k) O(k)

Common mistakes

Mistake What you see (real) Why Fix
Sort once, join in order 39 instead of 36 joined pieces are not small two smallest now: a heap
Max-heap 46 instead of 30 long pieces end up deep default (min) PriorityQueue
Joined piece not put back 5 and 17 pieces vanish heap.add(a + b)
int total a negative cost overflow past 2³¹ − 1 long
C++ priority_queue without greater<> max-heap behaviour C++ default is a max-heap priority_queue<T, vector<T>, greater<T>>
Huffman with one distinct letter empty code "" the root is a leaf give it the code "0"

Mini project: compress and decompress

Encode a sentence to bits with Huffman codes, then decode by walking the tree.

import java.util.*;

public class Main {
    // Mini project: Huffman encode + decode a sentence; prints sizes and checks the round trip.
    record Node(int freq, char ch, Node left, Node right) {}
    static Map<Character, String> codes = new HashMap<>();
    static void walk(Node n, String code) {
        if (n.left() == null) { codes.put(n.ch(), code.isEmpty() ? "0" : code); return; }
        walk(n.left(), code + "0");
        walk(n.right(), code + "1");
    }
    public static void main(String[] args) {
        String text = "chai and samosa and more chai";
        Map<Character, Integer> freq = new TreeMap<>();
        for (char c : text.toCharArray()) freq.merge(c, 1, Integer::sum);
        PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> x.freq() != y.freq() ? x.freq() - y.freq() : x.ch() - y.ch());
        for (var e : freq.entrySet()) heap.add(new Node(e.getValue(), e.getKey(), null, null));
        while (heap.size() > 1) {
            Node a = heap.poll(), b = heap.poll();
            heap.add(new Node(a.freq() + b.freq(), (char) Math.min(a.ch(), b.ch()), a, b));
        }
        Node root = heap.poll();
        walk(root, "");
        StringBuilder bits = new StringBuilder();
        for (char c : text.toCharArray()) bits.append(codes.get(c));
        StringBuilder back = new StringBuilder();
        Node cur = root;
        for (char b : bits.toString().toCharArray()) {
            cur = b == '0' ? cur.left() : cur.right();
            if (cur.left() == null) { back.append(cur.ch()); cur = root; }
        }
        System.out.println(text.length() * 8 + " bits as ASCII, " + bits.length() + " bits as Huffman");
        System.out.println("decoded: " + back + " (same: " + back.toString().equals(text) + ")");
    }
}
232 bits as ASCII, 99 bits as Huffman
decoded: chai and samosa and more chai (same: true)

Practice

1. Last Stone Weight (LeetCode 1046). Smash the two heaviest stones; if they differ, the difference goes back. Return the last stone's weight (or 0).

Solution

A max-heap this time.

import heapq

# Last Stone Weight (LeetCode 1046): max-heap via negated values.
def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = -heapq.heappop(heap)
        b = -heapq.heappop(heap)
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

print(last_stone_weight([2, 7, 4, 1, 8, 1]))
print(last_stone_weight([1]))
print(last_stone_weight([3, 3]))
1
1
0

2. Optimal file merging. Merging two files of sizes a and b copies a + b bytes. Merge files of sizes [20, 30, 10, 5, 30] with the least copying. Hint: today's heap rule; the answer is 205.

Solution
import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Long> heap = new PriorityQueue<>(List.of(20L, 30L, 10L, 5L, 30L));
        long copied = 0;
        while (heap.size() > 1) {
            long a = heap.poll(), b = heap.poll();
            copied += a + b;
            System.out.println("merge " + a + " + " + b + " = " + (a + b));
            heap.add(a + b);
        }
        System.out.println("copied: " + copied);
    }
}
merge 5 + 10 = 15
merge 15 + 20 = 35
merge 30 + 30 = 60
merge 35 + 60 = 95
copied: 205

3. Decode Huffman bits. Given the tree and a bit string, walk from the root (0 = left, 1 = right) and emit a letter at every leaf (see the mini project).

Quick quiz

Pieces [1, 2, 3, 4]. Minimum cost? A) 19 B) 20 C) 17 D) 10

Answer

A) 19. 1+2 = 3 (pay 3), 3+3 = 6 (pay 6), 4+6 = 10 (pay 10): 3 + 6 + 10 = 19.

Interview questions

  1. Why does joining the two smallest work? Each piece is paid once per join above it; the exchange argument puts the two smallest deepest without increasing the cost.
  2. Why isn't sorting once enough? Joined pieces re-enter the pool and may no longer be the smallest; a heap keeps "smallest now" correct.
  3. Complexity? n − 1 joins × O(log n) heap operations = O(n log n); O(n) space.
  4. What makes Huffman codes decodable? They're prefix-free: letters sit only at leaves.
  5. Is the Huffman tree unique? No; ties can give different trees, but all have the same minimum total bits.
  6. Java vs C++ default heap? Java PriorityQueue is a min-heap; C++ priority_queue is a max-heap.
  7. Why long? Sums of many joins exceed Integer.MAX_VALUE.

Glossary

Term Meaning
Min-heap / priority queue Always gives the smallest item, O(log n) per operation
poll / add Remove the smallest / insert
Greedy Best choice now, never undone
Exchange argument Proof by swapping the greedy choice into an optimal answer
Depth Number of joins (edges) above a leaf
Integer overflow A value past the type's limit wraps around
Bit / ASCII 0 or 1 / 8 bits per character
Prefix-free code No code starts another
Huffman coding Optimal prefix-free code: merge the two rarest
record A compact Java data class

Summary

  • Each join costs both lengths; every piece is paid once per join above it.
  • Trying every order times out; sort once, join in order is a trap (39 instead of 36).
  • Always join the two smallest now with a min-heap: O(n log n), and use long.
  • Huffman coding is the same rule on letter counts: abracadabra in 23 bits instead of 88.
  • Next episode: dynamic programming 1: Fibonacci, memoization vs tabulation, climbing stairs.