GeeksforGeeks: HardGreedy

Huffman Coding

Problem in Plain English

Build a Huffman prefix-code tree from distinct symbols and their frequencies. Return leaf codes in preorder, using original symbol positions to resolve equal frequencies.

Problem Statement

This page solves GeeksforGeeks Huffman Encoding. Given distinct symbols s and corresponding frequencies f, repeatedly combine the two nodes of least frequency into a parent whose frequency is their sum. The smaller node goes left. For equal frequencies, the subtree containing the earliest symbol in the original string goes left. Return the leaf codes in left-before-right preorder, assigning 0 to a left edge and 1 to a right edge. The output is in tree order, not in the order of s.

The statement does not state a frequency magnitude bound. Its linked official article resolves the singleton convention as code 0. Here frequencies are nonnegative integer counts; merged weights use exact arithmetic. With one symbol the root is already a leaf: emit 0 rather than the mathematical empty path, following that official article. The published GFG Java wrapper accepts int frequencies; the JavaScript method additionally accepts BigInt or decimal strings for exact larger counts.

Constraints

1 <= s.length = f.length <= 26; symbols are distinct.
The official statement gives no numeric frequency bound; do not infer one from the examples.
These solutions assume nonnegative integer frequencies and preserve their exact sums. Java uses the official int[] signature and BigInteger internally.

Examples

Example 1

Input: s = "abcdef", f = [5,9,12,13,16,45]
Output: ["0","100","101","1100","1101","111"]

Preorder leaves are f,c,d,a,b,e. The weighted path length is 45 + 24 + 26 + 20 + 36 + 48 = 199.

Example 2

Input: s = "x", f = [7]
Output: ["0"]

The singleton root has no edges, but the linked official article assigns code 0 so the symbol has a nonempty code.

Example 3

Input: s = "abcd", f = [1,1,2,2]
Output: ["0","100","101","11"]

Merge a and b to weight 2 with earliest index 0. It precedes c at index 2 among weight-2 nodes; merging that parent with c gives weight 4. Then d (2) goes left of that parent (4). Preorder is d,a,b,c with codes 0,100,101,11.

Example 4

Input: s = "abcd", f = [1,1,1,1]
Output: ["00","01","10","11"]

Pairs (a,b) and (c,d) each weigh 2. The subtree containing a goes left of the subtree containing c, yielding codes in symbol order.

Intuition

A prefix code gives each symbol a root-to-leaf bit path; no leaf path can be the prefix of another leaf path. Frequent symbols should have shorter paths because each extra edge costs that symbol one bit per occurrence. The least frequent pair can be deepest siblings, so merge them into one temporary symbol and repeat. In Example 1 the 5 and 9 leaves merge to 14, while the 45 leaf eventually becomes the root’s left child with code 0. Keep the actual child pointers: the sum of merge costs measures compression cost but cannot produce the codes.

Approaches

Huffman Tree

Optimal

Solution Details

Reveal Huffman Tree: intuition, complexity, and code

Intuition

Order nodes by (frequency, earliest original symbol index), merge two minima, and traverse the resulting tree to emit paths. Each subtree remembers its smallest leaf index, so ties between internal nodes and leaves obey the same rule. Subtrees in the queue have disjoint leaves, so their earliest indices are different and this ordering is total. A min-heap supports each removal and insertion in logarithmic time. JavaScript includes the heap implementation rather than relying on an unavailable judge helper.

Step-by-Step Logic

Queue leaves with weights 5,9,12,13,16,45 and original indices 0 through 5.
Remove 5 and 9, create parent 14 with children a,b; remove 12 and 13, create parent 25 with children c,d.
Remove 14 and 16, create parent 30 with children (a,b),e.
Remove 25 and 30, create parent 55; then remove 45 and 55 to create root 100.
Traverse left first: f has 0; c,d have 100,101; a,b have 1100,1101; e has 111.
Return the preorder leaf list ["0","100","101","1100","1101","111"].

Why It Works

For nonnegative frequencies, take a minimum-weight prefix tree and select two sibling leaves at maximum depth. Exchanging the two least frequent symbols with these deepest siblings cannot increase weighted path length: assigning a smaller weight to a longer path is no more costly. Thus some optimum has the least frequent pair as siblings. Contract them to one leaf of summed weight. Expanding that leaf adds exactly the two frequencies to total cost, regardless of the contracted tree, so an optimal contracted tree gives an optimal original tree. Induct on the number of leaves using the mathematical edge-depth objective, whose contracted singleton has depth zero. The user-facing one-bit singleton convention is handled separately and does not add a bit during contraction. Frequency ties preserve cost; earliest-index ordering selects a deterministic optimum. Traversal outputs exactly one path per leaf, and distinct leaves cannot be ancestors of one another, proving the prefix property. For a singleton the official nonempty-code convention assigns 0; among nonempty binary codes a one-bit code is optimal.

Dry Run

Huffman Tree: variable states at each step
Action	Queue weights after action	Children or emitted codes
Initialize	5,9,12,13,16,45	a,b,c,d,e,f
Merge 5 + 9	12,13,14,16,45	14: a,b
Merge 12 + 13	14,16,25,45	25: c,d
Merge 14 + 16	25,30,45	30: (a,b),e
Merge 25 + 30	45,55	55: (c,d),((a,b),e)
Merge 45 + 55	100	root: f,55
Preorder leaves	empty	["0","100","101","1100","1101","111"]

Complexity Analysis

Time Complexity

O(n log n + L)

Space Complexity

O(n + L)

The heap builds 2n-1 nodes and performs n-1 merges. L is the total number of output bits, which can be quadratic for a skew tree; copied path strings are bounded by that output work. Tree/heap storage is linear plus returned codes and paths. Depth is at most n-1 (25), so recursion is safe. Arithmetic comparisons and additions also depend on frequency bit width for unbounded integers; the displayed bound counts arithmetic operations, not bit operations.

Code

Solution.java

1import java.math.BigInteger;2import java.util.ArrayList;3import java.util.PriorityQueue;4class Solution {5    private static class Node {6        BigInteger weight;7        int first;8        Node left, right;9        Node(BigInteger w, int i, Node l, Node r) {10            weight = w; first = i; left = l; right = r;11        }12    }13    public ArrayList<String> huffmanCodes(String s, int[] f) {14        PriorityQueue<Node> heap = new PriorityQueue<>((a, b) -> {15            int c = a.weight.compareTo(b.weight);16            return c != 0 ? c : Integer.compare(a.first, b.first);17        });18        for (int i = 0; i < f.length; i++)19            heap.add(new Node(BigInteger.valueOf(f[i]), i, null, null));20        while (heap.size() > 1) {21            Node a = heap.remove(), b = heap.remove();22            heap.add(new Node(a.weight.add(b.weight), Math.min(a.first, b.first), a, b));23        }24        ArrayList<String> codes = new ArrayList<>();25        emit(heap.remove(), "", codes);26        return codes;27    }28    private void emit(Node node, String path, ArrayList<String> codes) {29        if (node.left == null) { codes.add(path.isEmpty() ? "0" : path); return; }30        emit(node.left, path + "0", codes);31        emit(node.right, path + "1", codes);32    }33}

Hints

Hint 1

A code is a leaf path, so keep both children when you combine nodes.

Hint 2

Which two frequencies can occupy deepest sibling leaves without increasing the cost?

Hint 3

Merge the two minima using earliest original index for ties, then emit left-0 and right-1 paths in preorder.

Edge Cases

A singleton returns ["0"] under the linked official article’s convention; it does not return an empty list or an empty code.
Equal internal and leaf weights must compare earliest subtree indices, not creation order.
Zero counts still receive leaf codes; they do not invalidate the exchange argument.
Merged sums can overflow a fixed-width type even when each input frequency fits it.

Common Mistakes and Interview Tips

Returning only the sum of merged weights never constructs the requested codes.
Returning codes in s order differs from the source’s preorder output.
Using heap insertion order for ties can disagree with original-symbol subtree order.
Converting a rounded JavaScript Number to BigInt cannot restore the original frequency; supply exact input.

Key Takeaway

A greedy contraction needs an exchange argument and a way to expand the contracted solution. Retain structure, define ties for internal objects, and include the cost of producing the requested output.