Huffman Encoding Problem

Geeks for Geeks [Medium]

Problem Statement

Compress data using minimum bits using Huffman coding based on character frequencies.

Example: Characters = [a,b,c,d], Freq = [5,9,12,13] → Build Huffman Tree & codes.

Approach 1: Brute Force

Generate all possible prefix codes and select minimum weighted sum.

generate all possible prefix codes
calculate sum(freq * codeLength)
return minimum sum code

💡 Think: Consider all prefix-code assignments and choose the one with minimum weighted length.

Approach 2: Better

Sort characters by frequency and merge two smallest repeatedly.

create list of nodes with freq
while more than 1 node:
    pick two smallest nodes
    merge into new node with sum freq
    insert back
assign codes from tree

💡 Think: Repeatedly merge the two least frequent symbols to build the optimal tree.

Approach 3: Optimal Greedy

Use min-heap to efficiently build Huffman tree.

create min-heap of characters by freq
while heap size > 1:
    left = pop()
    right = pop()
    mergeNode = left.freq + right.freq
    push mergeNode
assign 0/1 to tree edges to get codes

💡 Think: Use a min-heap to extract two smallest frequencies, merge, and reinsert until one tree remains.

Solve on LeetCode