In this note, I category problems in LeetCode into groups that can be solved by one common technique/ algorithm. By technique and algorithm, I mean a specific and particular method, not a common one like dynamic programming/ binary search.

Merge Interval
  1. https://leetcode.com/problems/merge-intervals/ (medium)
        int i = 0;
        while (i < n) {
            int j = i;
            int end = a[i].second;
            
            while (j + 1 < n && a[j+1].first <= end) {
                j++;
                end = max(end, a[j].second);
            }
            res.push_back({ a[i].first, end });
            i = j + 1;
        }
  1. https://leetcode.com/problems/employee-free-time/ (hard)
  2. https://leetcode.com/problems/insert-interval/ (hard)
Interval-related problem (ad-hoc)
    vector<int> intersection(vector<int> a, vector<int> b) {
        if (a[1] < b[0]) return { };
        if (b[1] < a[0]) return { };
        if (a[0] >= b[0] && a[0] <= b[1]) return { a[0], min(a[1], b[1]) };
        return { b[0], min(b[1], a[1]) };
    }
  1. https://leetcode.com/problems/meeting-rooms/
  2. https://leetcode.com/problems/interval-list-intersections/ (medium)
  3. https://leetcode.com/problems/non-overlapping-intervals/
Merge k sorted list
        typedef pair<int, int> ii;
        typedef pair<int, ii> iii;
        
        priority_queue<iii, vector<iii>, greater<iii>> q;
        for(int i = 0; i < n-1; i++) 
            q.push(iii(a[i][0], ii(i, 0)));
        
        while (!q.empty()) {
            count++;
            int value = q.top().first;
            int row = q.top().second.first;
            int col = q.top().second.second;
            q.pop();
            if (col + 1 < a[row].size()) 
                q.push(iii(a[row][col + 1], ii(row, col + 1)));
        }
  1. https://leetcode.com/problems/merge-k-sorted-lists/ (hard)
  2. https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
  3. https://leetcode.com/problems/find-k-th-smallest-pair-distance/
  4. https://leetcode.com/problems/insert-interval/
Longest Common Subsequence
        int n = s.size();
        int m = t.size();
        if (m * n == 0) return 0;
        int fx[n+1][m+1];
        memset(fx, 0, sizeof(fx));
        fx[1][1] = (s[0] == t[0]);
        
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) {
                if (i == 1 && j == 1) continue;
                fx[i][j] = max(fx[i-1][j], fx[i][j-1]);
    
                if (s[i-1] == t[j-1])
                    fx[i][j] = max(fx[i][j], fx[i-1][j-1] + 1);
               // cout<<i<<" "<<j<<" "<<fx[i][j]<<endl;
            }
  1. https://leetcode.com/problems/longest-common-subsequence/
  2. https://leetcode.com/problems/delete-operation-for-two-strings/
  3. https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
Find sum by Two-pointer
        int n = a.size();
        int i = 0, j = n-1;
        while (i < j) {
            int sum = a[i] + a[j];
            if (sum <= target) {
                if (sum == target) {
                    vector<int> res = { i+1, j+1 };
                    return res;
                }
                i++;
            } else j--;
        }
  1. https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
  2. https://leetcode.com/problems/two-sum-less-than-k/
  3. https://leetcode.com/problems/3sum/
  4. https://leetcode.com/problems/3sum-closest/
  5. https://leetcode.com/problems/3sum-smaller/
  6. https://leetcode.com/problems/4sum
Duplicated item in array (1 ≤ a[i] ≤ n, no extra space)
        vector<int> res;
        for(int i = 0; i < nums.size(); i++) {
            int index = abs(nums[i]) - 1;
            nums[index] = -nums[index];
            if (nums[index] > 0) res.push_back(index+1);
        }
  1. https://leetcode.com/problems/find-all-duplicates-in-an-array/
  2. https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
Finding next-greater/ next-smaller index by Left-right technique
        int n = nums.size();
        int r[n];
        r[n-1] = n;
        for(int i = n-2; i >= 0; i--) {
            if (nums[i+1] > nums[i]) r[i] = i + 1;
            else {
                int j = i + 1;
                while (j != n && nums[j] <= nums[i]) j = r[j];
                r[i] = j;
            }
        }
  1. https://leetcode.com/problems/next-greater-element-i/
  2. https://leetcode.com/problems/Next-Greater-Element-II
  3. https://leetcode.com/problems/online-stock-span/
  4. https://leetcode.com/problems/132-pattern/
  5. https://leetcode.com/problems/maximal-rectangle/
  6. https://leetcode.com/problems/largest-rectangle-in-histogram/
BFS tree level by level
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
                int currentSize = q.size();
                vector<int> currentLevel;

                for(int i = 0; i < currentSize; i++) {
                    TreeNode* u = q.front();
                    q.pop();
                    if (u != NULL) {
                        currentLevel.push_back(u->val);
                        q.push(u->left);
                        q.push(u->right);
                    } else {
                        currentLevel.push_back(-1);
                    }
                }
            }
  1. https://leetcode.com/problems/symmetric-tree/
  2. https://leetcode.com/problems/binary-tree-level-order-traversal/
  3. https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
  4. https://leetcode.com/problems/binary-tree-right-side-view/
  5. https://leetcode.com/problems/n-ary-tree-level-order-traversal/
  6. https://leetcode.com/problems/find-bottom-left-tree-value/
  7. https://leetcode.com/problems/find-largest-value-in-each-tree-row/
Topo sort & circle detection
    vector<vector<int>> adj;
    vector<bool> visited;
    vector<bool> inDfs;
    vector<int> q;
    int id;
    bool ok;
    void dfs(int u) {
        visited[u] = true;
        inDfs[u] = true;
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (!visited[v]) {
                dfs(v);
            } else if (inDfs[v]) {
                ok = false;
                return;
            }
        }
        q[id--] = u;
        inDfs[u] = false;
    }
  1. https://leetcode.com/problems/course-schedule-ii/
  2. https://leetcode.com/problems/parallel-courses/
Add range trick
    for(auto update: updates) {
		int u = update[0];
		int v = update[1];
		int val = update[2];
		a[u]+=val;
		if (v+1 < length) a[v+1]-=val;
	}        
	for(int i = 1; i < length; i++)
		a[i] += a[i-1];
  1. https://leetcode.com/problems/range-addition/
  2. https://leetcode.com/problems/my-calendar-ii/
  3. https://leetcode.com/problems/my-calendar-iii/
Bucket find top K frequent items
        int n = a.size();
        unordered_map<int, int> count;
        for(int i: a) count[i]++;
        vector<int> res;
        
        vector<int> bucket[n+1];
        for(auto pair: count) {
            bucket[pair.second].push_back(pair.first);
        }
        
        for(int i = n; i >= 0 && res.size() < k; i--) {
            for(int j = 0; j < bucket[i].size(); j++) 
                res.push_back(bucket[i][j]);
        }
        
        return res;
  1. https://leetcode.com/problems/top-k-frequent-elements
  2. https://leetcode.com/problems/top-k-frequent-words/
  3. https://leetcode.com/problems/sort-characters-by-frequency/

<updating ...>