Where it runs
1. The problem
You store a lot of text and want it to take less space. The plain way gives every letter the same number of bits: 8 bits for an e and 8 bits for a z. Yet e shows up all the time and z almost never. A letter you use ten thousand times costs as much as a letter you use twice.
It pays to give common letters short codes and rare letters long ones. That is how gzip, zip and PNG shrink files. Two things are left to decide. The total number of bits should come out as small as possible. And a reader has to split the stream of bits back into letters, although there are no marks between the codes.
The second condition is easy to break. Say e is 0 and some other letter is 01. A reader sees 01 and can't tell whether that is e followed by the start of the next code, or the other letter. So no code may be the start of another code.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- fewest coins or pieces to make an amount
- largest that still fits, taken greedily
- make change with denominations
- prove optimality with an exchange argument
Looks similar, isn't
- Dynamic programming (1-D)
DP keeps every option open until the end. Greedy commits at once and cannot undo.
- Backtracking
Backtracking tries every choice and keeps the best. Greedy tries one and trusts it.
- Sort with a custom comparator
Most greedy solutions begin with a sort. The comparator is where the choice is written.
- Binary search on the answer
There the feasibility test is often greedy itself. The search only picks the value to test.
O(n log n) when the input has to be sorted first. The pass afterwards is a single loop, O(n).
On LeetCode
LeetCode has no free problem that builds Huffman codes. The two closest ones, Minimum Cost to Connect Sticks (1167) and Minimum Time to Build Blocks (1199), are premium. The heap step Huffman repeats, joining the two smallest, has free problems in lesson 109.