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
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;
}
- https://leetcode.com/problems/employee-free-time/ (hard)
- 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]) };
}
- https://leetcode.com/problems/meeting-rooms/
- https://leetcode.com/problems/interval-list-intersections/ (medium)
- 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)));
}
- https://leetcode.com/problems/merge-k-sorted-lists/ (hard)
- https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
- https://leetcode.com/problems/find-k-th-smallest-pair-distance/
- 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;
}
- https://leetcode.com/problems/longest-common-subsequence/
- https://leetcode.com/problems/delete-operation-for-two-strings/
- 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--;
}
- https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
- https://leetcode.com/problems/two-sum-less-than-k/
- https://leetcode.com/problems/3sum/
- https://leetcode.com/problems/3sum-closest/
- https://leetcode.com/problems/3sum-smaller/
- 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);
}
- https://leetcode.com/problems/find-all-duplicates-in-an-array/
- 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;
}
}
- https://leetcode.com/problems/next-greater-element-i/
- https://leetcode.com/problems/Next-Greater-Element-II
- https://leetcode.com/problems/online-stock-span/
- https://leetcode.com/problems/132-pattern/
- https://leetcode.com/problems/maximal-rectangle/
- 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);
}
}
}
- https://leetcode.com/problems/symmetric-tree/
- https://leetcode.com/problems/binary-tree-level-order-traversal/
- https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
- https://leetcode.com/problems/binary-tree-right-side-view/
- https://leetcode.com/problems/n-ary-tree-level-order-traversal/
- https://leetcode.com/problems/find-bottom-left-tree-value/
- 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;
}
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];
- https://leetcode.com/problems/range-addition/
- https://leetcode.com/problems/my-calendar-ii/
- 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;
- https://leetcode.com/problems/top-k-frequent-elements
- https://leetcode.com/problems/top-k-frequent-words/
- https://leetcode.com/problems/sort-characters-by-frequency/
<updating ...>
