Bonus Topics

Trie Structure: Character-by-Character Branching
  Insert: ['apple', 'app', 'apt', 'bat', 'bad']
          root
         /    \
        a      b
        |      |
        p      a
       / \    / \
      p   t  t   d
      |   |  *   *     (* = isEnd marker)
      l   *
      |
      e
      |
      *
‘app’  -> root->a->p->p*       (isEnd=true at second p)
‘apple’ -> root->a->p->p->l->e* (extends ‘app’ branch)
‘apt’  -> root->a->p->t*       (shares ‘ap’ with above)
Search ‘app’: traverse a->p->p, check isEnd -> true.
StartsWith ‘ap’: traverse a->p, node exists -> true.
Search ‘ap’: traverse a->p, isEnd=false -> false.

```cpp // 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
}

};

</div>
<h3>A.3 — Word Search II (Trie + Backtracking)</h3>
<div class="ch-code-wrap">
```cpp
// 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: Union by Rank + Path Compression
  Elements: {0, 1, 2, 3, 4, 5}  Initially each element is its own set.
  parent = [0, 1, 2, 3, 4, 5]   rank = [0, 0, 0, 0, 0, 0]
union(0, 1):  find(0)=0, find(1)=1. rank equal -> parent[1]=0, rank[0]++.
union(2, 3):  find(2)=2, find(3)=3. parent[3]=2, rank[2]++.
union(0, 2):  find(0)=0, find(2)=2. parent[2]=0, rank[0]++.
parent = [0, 0, 0, 2, 4, 5]
find(3) with PATH COMPRESSION:
find(3) -> parent[3]=2 -> parent[2]=0 -> root=0.
Compress: parent[3] = 0, parent[2] = 0.
parent = [0, 0, 0, 0, 4, 5]   (3 now directly points to root 0)
Sets: Set A: {0, 1, 2, 3}   Set B: {4}   Set C: {5}

```cpp // Union-Find with Union by Rank + Path Compression // find: amortised O(alpha(n)) ~ O(1) unite: amortised O(alpha(n)) class UnionFind { vector 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; }

};

</div>
<h3>B.3 — Number of Islands Using Union-Find</h3>
<div class="ch-code-wrap">
```cpp
// 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
}

Monotonic Stack: Next Greater Element Trace
  Array: [2, 1, 5, 6, 2, 3]
  Goal: find Next Greater Element (NGE) for each index.
Use a DECREASING monotonic stack. Stack stores INDICES.
When we pop index j because nums[i] > nums[j], nums[i] is the NGE for j.
i=0: nums[0]=2. Stack empty. Push 0.        stack=[0]    (values: [2])
i=1: nums[1]=1. 1 < nums[top]=2 -> push 1.  stack=[0,1]  (values: [2,1])
i=2: nums[2]=5. 5 > nums[1]=1 -> pop 1, NGE[1]=5.
5 > nums[0]=2 -> pop 0, NGE[0]=5.
Stack empty. Push 2.        stack=[2]    (values: [5])
i=3: nums[3]=6. 6 > nums[2]=5 -> pop 2, NGE[2]=6. Push 3.
i=4: nums[4]=2. 2 < nums[3]=6 -> push 4.    stack=[3,4]
i=5: nums[5]=3. 3 > nums[4]=2 -> pop 4, NGE[4]=3. Push 5.
End: remaining {3,5} have no NGE -> NGE[3]=NGE[5]=-1.
Result: NGE = [5, 5, 6, -1, 3, -1]
Each element pushed and popped at most once -> O(n) total.

```cpp // Next Greater Element I (LC 496) — O(n) vector nextGreaterElement(vector& nums1, vector& nums2) { unordered_map nge; // nge[val] = next greater element value stack 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 res; for (int x : nums1) res.push_back(nge.count(x) ? nge[x] : -1); return res; } ```

```cpp // LeetCode 739 — Daily Temperatures // For each day, how many days until a warmer temperature? // Time: O(n) Space: O(n) vector dailyTemperatures(vector& temps) { int n = temps.size(); vector res(n, 0); stack 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) } ```

```cpp // ── FIXED WINDOW: Maximum sum subarray of size k ──────────── // Time: O(n) Space: O(1) int maxSumFixed(vector& 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); }

</div>
</section>
<!-- TOPIC E: TWO POINTERS -->
<section id="topic-e" class="chapter-section">
<h2> Topic E — Two Pointers</h2>
<h3>E.1 — Two Pointer Patterns</h3>
<p><strong>Two pointers</strong> uses two indices that move through a data structure, typically towards each other or in the same direction. This eliminates the inner loop of an O(n²) solution when the data has monotone properties (sorted array, or a constraint that improves/worsens as pointers move).</p>
<div class="table-responsive">
<table class="insight-table">
<thead>
<tr>
<th>Pattern</th>
<th>Pointer motion</th>
<th>Classic problems</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>Opposite ends (converge)</strong></td>
<td>lo starts left, hi starts right; move toward each other</td>
<td>Two Sum (sorted), Container With Most Water, 3Sum</td>
</tr>
<tr>
<td><strong>Same direction (fast/slow)</strong></td>
<td>Both move left-to-right at different speeds</td>
<td>Remove duplicates, find middle of linked list, cycle detection</td>
</tr>
<tr>
<td><strong>Partition</strong></td>
<td>lo tracks write position, hi reads</td>
<td>Dutch National Flag, partition for QuickSort</td>
</tr>
</tbody>
</table>
</div>
<div class="ch-code-wrap">
```cpp
// ── 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;
}

```cpp 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 } };

</div>
<p><strong>Complexity:</strong> Time O(L) per operation, Space O(total_chars * 26)</p>
</section>
<!-- SOLVED PROBLEM 2 -->
<section id="solved-2" class="chapter-section">
<h2> Solved Problem 2: Number of Connected Components</h2>
<p>Given n nodes (0 to n-1) and a list of undirected edges, return the number of connected components. (LeetCode 323 — Medium)</p>
<div class="insight-box">
<h4>OBSERVATIONS</h4>
<ul>
<li>Classic Union-Find application: initialise n components (each node is its own set), then for each edge union the two endpoints. Final component count = answer.</li>
<li>Alternative: BFS/DFS counting visited components. Both O(V+E). Union-Find is cleaner for dynamic edge-addition scenarios.</li>
<li>Every time <code>unite(a,b)</code> successfully merges two different sets, the component count decreases by 1. Start from n, apply all edges.</li>
</ul>
</div>
<div class="ch-code-wrap">
```cpp
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;
    }
};

```cpp class Solution { public: int largestRectangleArea(vector& heights) { heights.push_back(0); // sentinel forces complete flush stack 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; } }; ```