Questions given

Huffman Encoding

Difficulty: Hard Time: 30mintues

Given a string s of distinct characters and their corresponding frequency f[ ] i.e. character s[i] has f[i] frequency. You need to build the Huffman tree and return all the huffman codes in preorder traversal of the tree.Note: While merging, if two nodes have the same value (frequency), then the node whose subtree contains the character that appears earlier in the string s will be taken on the left of the Binary Tree and the other one to the right. Otherwise, the node with smaller value will be taken on the left of the subtree and the other one to the right.

SOLVE

Brute Force Approach ( O(N2))

Intuition:

Think of this like having a pile of cards on a table. To build the tree, you manually look through every single card to find the two with the smallest numbers. You tape them together, write their sum on a new card, and throw it back into the pile. You repeat this until only one giant taped-together block remains.

Approach:

1. Storage: Store all nodes in a simple std::vector or list.

2. Search: In every iteration, perform a linear scan (a for loop) through the entire list to find the two nodes with the lowest frequencies.

3. Merge: Create a parent node for these two, remove the two children from the list, and add the parent.

4. Repeat: Do this  times until only the root remains.

   N−1
   

Why is it O(N2)

Because you have to find the minimum N times, and each search takes O(N) time.

CODE

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

// 1. Define the Node structure
struct Node {
    int data; // frequency
    int index; // original index for tie-breaking
    Node *left, *right;

    Node(int d, int i) : data(d), index(i), left(nullptr), right(nullptr) {}

    Node(Node* l, Node* r) {
        data = l->data + r->data;
        index = min(l->index, r->index);
        left = l;
        right = r;
    }
};

// 2. Comparator for the Min-Heap
struct Compare {
    bool operator()(Node* a, Node* b) {
        if (a->data != b->data)
            return a->data > b->data; // Smaller frequency first
        return a->index > b->index;    // Tie-break with original index
    }
};

class Solution {
    // Helper function for Preorder traversal
    void preOrder(Node* root, vector<string>& ans, string curr) {
        if (!root) return;
        if (!root->left && !root->right) {
            ans.push_back(curr);
            return;
        }
        preOrder(root->left, ans, curr + '0');
        preOrder(root->right, ans, curr + '1');
    }

public:
    // FIX: Changed from (S, f, N) to (S, f) to match the driver call
    vector<string> huffmanCodes(string S, vector<int> f) {
        int n = f.size();
        priority_queue<Node*, vector<Node*>, Compare> pq;

        for (int i = 0; i < n; i++) {
            pq.push(new Node(f[i], i));
        }

        while (pq.size() > 1) {
            Node* left = pq.top(); pq.pop();
            Node* right = pq.top(); pq.pop();
            pq.push(new Node(left, right));
        }

        vector<string> ans;
        preOrder(pq.top(), ans, "");
        return ans;
    }
};