Bonus Topics

// Trie — O(L) per operation
// Insert/Search/StartsWith: O(L) time, O(L) space per word
struct TrieNode {
    TrieNode* children[26] = {};  // null = child doesn't exist
    bool isEnd = false;
};

class Trie {
    TrieNode* root;
public:
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx])
                cur->children[idx] = new TrieNode();
            cur = cur->children[idx];
        }
        cur->isEnd = true;
    }

    bool search(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return cur->isEnd;   // must be a complete word
    }

    bool startsWith(const string& prefix) {
        TrieNode* cur = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return true;  // prefix exists, word completeness irrelevant
    }
};

// LeetCode 212 — Word Search II
// Find all words from a dictionary that exist in a 2D grid.
// Time: O(M*N * 4^L)  L=longest word  Space: O(total chars in dict)
struct TrieNode {
    TrieNode* ch[26] = {};
    string word;  // non-empty = this node is end of a word
};

class Solution {
    void dfs(vector<vector<char>>& g, TrieNode* node,
             int r, int c, vector<string>& res) {
        if (r<0||r>=(int)g.size()||c<0||c>=(int)g[0].size()) return;
        char ch = g[r][c];
        if (ch=='#' || !node->ch[ch-'a']) return; // visited or no prefix
        node = node->ch[ch-'a'];
        if (!node->word.empty()) {                // found a complete word
            res.push_back(node->word);
            node->word = "";  // de-duplicate
        }
        g[r][c] = '#';  // mark visited
        dfs(g,node,r+1,c,res); dfs(g,node,r-1,c,res);
        dfs(g,node,r,c+1,res); dfs(g,node,r,c-1,res);
        g[r][c] = ch;   // restore
    }
public:
    vector<string> findWords(vector<vector<char>>& board,
                             vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {            // build trie
            TrieNode* cur = root;
            for (char c : w) {
                if (!cur->ch[c-'a']) cur->ch[c-'a'] = new TrieNode();
                cur = cur->ch[c-'a'];
            }
            cur->word = w;
        }
        vector<string> res;
        for (int r=0;r<(int)board.size();r++)
            for (int c=0;c<(int)board[0].size();c++)
                dfs(board, root, r, c, res);
        return res;
    }
};

// Union-Find with Union by Rank + Path Compression
// find: amortised O(alpha(n)) ~ O(1)   unite: amortised O(alpha(n))
class UnionFind {
    vector<int> parent, rank_;
    int components;
public:
    UnionFind(int n) : parent(n), rank_(n,0), components(n) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }

    // Path compression: make every node on the find-path point to root
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // recursive compression
        return parent[x];
    }

    // Union by rank: attach smaller tree under larger tree
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false; // already in same set
        if (rank_[ra] < rank_[rb]) swap(ra, rb);
        parent[rb] = ra;             // attach rb under ra
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        components--;
        return true;
    }

    bool connected(int a, int b) { return find(a) == find(b); }
    int  count()                 { return components; }
};

// LeetCode 200 — Number of Islands (Union-Find approach)
// Time: O(M*N * alpha(M*N))  Space: O(M*N)
int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size();
    UnionFind uf(m * n);
    int water = 0;
    int dr[] = {0, 1, 0, -1};
    int dc[] = {1, 0, -1, 0};
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '0') { water++; continue; }
            for (int d = 0; d < 4; d++) {
                int nr = r+dr[d], nc = c+dc[d];
                if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]=='1')
                    uf.unite(r*n+c, nr*n+nc); // merge adjacent land
            }
        }
    }
    return uf.count() - water; // subtract water cells
}

// Next Greater Element I (LC 496) — O(n)
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int,int> nge; // nge[val] = next greater element value
    stack<int> stk;             // decreasing monotonic stack of VALUES
    for (int x : nums2) {
        while (!stk.empty() && stk.top() < x) {
            nge[stk.top()] = x; // x is NGE for stk.top()
            stk.pop();
        }
        stk.push(x);
    }
    vector<int> res;
    for (int x : nums1) res.push_back(nge.count(x) ? nge[x] : -1);
    return res;
}

// LeetCode 739 — Daily Temperatures
// For each day, how many days until a warmer temperature?
// Time: O(n)  Space: O(n)
vector<int> dailyTemperatures(vector<int>& temps) {
    int n = temps.size();
    vector<int> res(n, 0);
    stack<int> stk; // decreasing monotonic stack of indices
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && temps[i] > temps[stk.top()]) {
            int j = stk.top(); stk.pop();
            res[j] = i - j; // days to wait = i - j
        }
        stk.push(i);
    }
    return res; // indices still in stack: res[j]=0 (never warmer)
}

// ── FIXED WINDOW: Maximum sum subarray of size k ────────────
// Time: O(n)  Space: O(1)
int maxSumFixed(vector<int>& nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];  // initial window
    int best = sum;
    for (int i = k; i < (int)nums.size(); i++) {
        sum += nums[i] - nums[i-k];  // slide: add right, remove left
        best = max(best, sum);
    }
    return best;
}

// ── VARIABLE WINDOW: Longest substring without repeating chars ─
// Time: O(n)  Space: O(min(n, charset))
int lengthOfLongestSubstring(string s) {
    unordered_map<char,int> freq;
    int lo = 0, best = 0;
    for (int hi = 0; hi < (int)s.size(); hi++) {
        freq[s[hi]]++;
        while (freq[s[hi]] > 1) {  // constraint violated: shrink left
            freq[s[lo]]--;
            lo++;
        }
        best = max(best, hi - lo + 1);
    }
    return best;
}

// ── VARIABLE WINDOW: Minimum Window Substring (LC 76) ────────
// Time: O(n)  Space: O(charset)
string minWindow(string s, string t) {
    unordered_map<char,int> need, have;
    for (char c : t) need[c]++;
    int formed = 0, required = need.size();
    int lo = 0, minLen = INT_MAX, start = 0;
    for (int hi = 0; hi < (int)s.size(); hi++) {
        char c = s[hi];
        have[c]++;
        if (need.count(c) && have[c] == need[c]) formed++;
        while (formed == required) {  // valid window: try to shrink
            if (hi - lo + 1 < minLen) { minLen = hi-lo+1; start = lo; }
            have[s[lo]]--;
            if (need.count(s[lo]) && have[s[lo]] < need[s[lo]]) formed--;
            lo++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

// ── OPPOSITE ENDS: Two Sum on sorted array ──────────────────
// Time: O(n)  Space: O(1)
vector<int> twoSumSorted(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size()-1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        if      (sum == target) return {lo+1, hi+1}; // 1-indexed
        else if (sum <  target) lo++;  // need larger sum
        else                   hi--;  // need smaller sum
    }
    return {};
}

// ── SAME DIRECTION: Remove duplicates from sorted array ──────
// Time: O(n)  Space: O(1)
int removeDuplicates(vector<int>& nums) {
    int lo = 0;  // write pointer
    for (int hi = 1; hi < (int)nums.size(); hi++) {
        if (nums[hi] != nums[lo]) {  // new unique element
            lo++;
            nums[lo] = nums[hi];
        }
    }
    return lo + 1; // new length
}

// ── FAST/SLOW: Floyd's cycle detection ───────────────────────
// Time: O(n)  Space: O(1)
bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // cycle detected
    }
    return false;
}

class Trie {
    struct Node {
        Node* ch[26] = {};
        bool isEnd = false;
    };
    Node* root = new Node();

    Node* traverse(const string& s) {  // returns node after last char or null
        Node* cur = root;
        for (char c : s) {
            if (!cur->ch[c-'a']) return nullptr;
            cur = cur->ch[c-'a'];
        }
        return cur;
    }
public:
    void insert(string word) {
        Node* cur = root;
        for (char c : word) {
            if (!cur->ch[c-'a']) cur->ch[c-'a'] = new Node();
            cur = cur->ch[c-'a'];
        }
        cur->isEnd = true;
    }
    bool search(string word) {
        Node* end = traverse(word);
        return end && end->isEnd;   // path exist AND complete word
    }
    bool startsWith(string prefix) {
        return traverse(prefix) != nullptr; // path existence is sufficient
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int> parent(n), rank_(n, 0);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find = [&](int x) -> int {
            if (parent[x] != x) parent[x] = find(parent[x]); // path compress
            return parent[x];
        };

        int components = n;
        for (auto& e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) continue; // already connected: skip
            if (rank_[ra] < rank_[rb]) swap(ra, rb);
            parent[rb] = ra;
            if (rank_[ra] == rank_[rb]) rank_[ra]++;
            components--;
        }
        return components;
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);  // sentinel forces complete flush
        stack<int> stk;        // increasing monotonic stack of indices
        int maxArea = 0;
        for (int i = 0; i < (int)heights.size(); i++) {
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                int h = heights[stk.top()]; stk.pop();
                // Width: from after current stack top to just before i
                int w = stk.empty() ? i : i - stk.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            stk.push(i);
        }
        return maxArea;
    }
};