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
PriorityQueueis 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
intholds up to 2,147,483,647 (about 214 crore); past that it wraps to negative.longholds 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, the1is 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
- 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.
- 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.
- Complexity? n − 1 joins × O(log n) heap operations = O(n log n); O(n) space.
- What makes Huffman codes decodable? They're prefix-free: letters sit only at leaves.
- Is the Huffman tree unique? No; ties can give different trees, but all have the same minimum total bits.
- Java vs C++ default heap? Java
PriorityQueueis a min-heap; C++priority_queueis a max-heap. - Why
long? Sums of many joins exceedInteger.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 (
39instead of36). - 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:
abracadabrain 23 bits instead of 88. - Next episode: dynamic programming 1: Fibonacci, memoization vs tabulation, climbing stairs.