- quick habit: whenever you use array for counting, always write array<int,26> cnt{}; (with {}) so you never forget initialization.
- size() vs length()
* For string: .size() == .length()
* For general containers: .size() exists, .length() usually doesn’t
* Watch out for unsigned type (size_t) in comparisons and indexing
Better:
int n = s.size(); // possible warning: conversion from size_t to int
size_t n = s.size(); //or int n = (int)s.size();
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// put helpers here
};
int main(){
return 0;
}Use when: anagrams, duplicates, “count occurrences”.
unordered_map<char,int> cnt;
for (char c : s) cnt[c]++;
for (auto &p : cnt) {
char ch = p.first;
int freq = p.second;
}217. Contains Duplicate
242. Valid Anagram
387. First Unique Character in a String
383. Ransom Note
349. Intersection of Two Arrays
If the problem asks about:
anagrams / permutations
duplicates / unique
“can we build string A from string B”
first/non-repeating
intersection counts
…it’s almost always a counting problem.
array<int,26> cnt{};
for (char c : s) cnt[c - 'a']++;array<int,256> cnt{};
for (unsigned char c : s) cnt[c]++;unordered_map<int,int> cnt;
for (int x : nums) cnt[x]++;note that arrays are initialised with {} but unordered_map need not.
- array<int,N> cnt; → elements uninitialized → use cnt{} or fill(0)
- unordered_map<K,V> cnt; → starts empty → safe; counts become 0 when first inserted via cnt[key]
- Important nuance: unordered_map also has {} but it’s optional
unordered_map<int,int> a; // empty
unordered_map<int,int> b{}; // also empty- in unordered_map, when we do
cnt[x]++;operator[] does this: * if key x doesn’t exist, it inserts x with default value 0 (for int) * then increments it
Use when: “find pair with sum”, or need previous seen index.
vector<int> twoSum(vector<int>& a, int target) {
unordered_map<int,int> pos;
for (int i = 0; i < (int)a.size(); i++) {
int need = target - a[i];
if (pos.count(need)) return {pos[need], i};
pos[a[i]] = i;
}
return {};
}1.Two Sum
217. Contains Duplicate
219. Contains Duplicate II
242. Valid Anagram
409. Longest Palindrome
Use when: sorted array, palindrome, reverse, pair sum in sorted.
int l = 0, r = (int)a.size() - 1;
while (l < r) {
// use a[l], a[r]
if (/*move left*/) l++;
else r--;
}Valid Palindrome (LeetCode 125))
Two Sum II – Input Array Is Sorted (LeetCode 167)
Reverse String (LeetCode 344)
Squares of a Sorted Array (LeetCode 977)
Remove Duplicates from Sorted Array (LeetCode 26)
Use when: longest/shortest subarray/substring satisfying condition.
int l = 0;
for (int r = 0; r < n; r++) {
// add a[r] to window
while (l <= r && /*window invalid*/) {
// remove a[l] from window
l++;
}
// window [l..r] is valid here -> update answer
}Common variant: “at most K” with frequency map: (Subarrays with At Most K Distinct Integers)
int atMostKDistinct(const vector<int>& a, int K) {
unordered_map<int,int> cnt;
int l = 0;
long long ans = 0;
for (int r = 0; r < (int)a.size(); r++) {
cnt[a[r]]++;
while ((int)cnt.size() > K) {
if (--cnt[a[l]] == 0) cnt.erase(a[l]);
l++;
}
ans += (r - l + 1); // number of valid subarrays ending at r
}
return (int)ans;
}643. Maximum Average Subarray I
Why it fits: fixed-size window k; expand r, once window size > k shrink l.
Core pattern: maintain sum of current window.
121. Best Time to Buy and Sell Stock
Why it fits: r scans prices; l tracks best buy point; when prices[r] < prices[l], move l = r.
Core pattern: maximize prices[r] - prices[l].
485. Max Consecutive Ones
Why it fits: simplest “window of 1s”; expand r; reset/shrink when you hit 0.
Core pattern: count current streak / or use l reset.
1004. Max Consecutive Ones III
Why it fits: variable-size window with constraint “at most k zeros”; expand r, if zeros > k then shrink l.
Core pattern: maintain zeroCount and enforce zeroCount <= k.
424. Longest Repeating Character Replacement
Why it fits: variable window; expand r, track char frequencies; if replacements needed exceed k, shrink l.
Core pattern: keep maxFreq in window; valid if windowLen - maxFreq <= k.
Use when: many range sum queries, or subarray sums.
vector<long long> pref(n+1, 0);
for (int i = 0; i < n; i++) pref[i+1] = pref[i] + a[i];
// sum of a[l..r]
auto rangeSum = [&](int l, int r) -> long long {
return pref[r+1] - pref[l];
};303. Range Sum Query – Immutable
Why prefix sum fits: You precompute prefix[i] = sum(nums[0..i-1]), then any range sum is prefix[r+1] - prefix[l] in O(1).
Pattern: Many queries on a fixed array.
1480. Running Sum of 1d Array
Why prefix sum fits: It literally asks you to compute prefix sums (running totals).
Pattern: “Build prefix sums” in its simplest form.
724. Find Pivot Index
Why prefix sum fits: Total sum and a running prefix sum let you check leftSum == totalSum - leftSum - nums[i].
Pattern: Compare left vs right sums efficiently.
1732. Find the Highest Altitude
Why prefix sum fits: Altitude changes are deltas; prefix-summing deltas gives altitude at each point; track max.
Pattern: Prefix sum over differences.
560. Subarray Sum Equals K
Why prefix sum fits: Use prefix sums + hashmap counts: number of prior prefixes equal to currentPrefix - k.
Pattern: Count subarrays with given sum (classic prefix sum + frequency map).
Use when: count subarrays with given sum / 0-sum etc.
int subarraySum(vector<int>& a, int k) {
unordered_map<long long,int> freq;
freq[0] = 1;
long long sum = 0;
int ans = 0;
for (int x : a) {
sum += x;
if (freq.count(sum - k)) ans += freq[sum - k];
freq[sum]++;
}
return ans;
}#1 Two Sum (Array + HashMap)
#20 Valid Parentheses (Stack)
#21 Merge Two Sorted Lists (Linked List / Two pointers)
#121 Best Time to Buy and Sell Stock (Greedy / One pass)
#217 Contains Duplicate (HashSet)
#560 Prefix sum + hashmap (Subarray Sum Equals K)
Use when: select non-overlapping, merge intervals, schedule.
Merge intervals:
vector<vector<int>> merge(vector<vector<int>>& in) {
sort(in.begin(), in.end());
vector<vector<int>> out;
for (auto &cur : in) {
if (out.empty() || out.back()[1] < cur[0]) out.push_back(cur);
else out.back()[1] = max(out.back()[1], cur[1]);
}
return out;
}56. Merge Intervals
252. Meeting Rooms (LeetCode Premium)
455. Assign Cookies
860. Lemonade Change
605. Can Place Flowers
Use when: “next greater element”, “daily temperatures”, ranges.
vector<int> nextGreater(const vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1);
stack<int> st; // indices, values decreasing
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = i;
st.pop();
}
st.push(i);
}
return ans;
}496 — Next Greater Element I
1475 — Final Prices With a Special Discount in a Shop
682 — Baseball Game
503 — Next Greater Element II
739 — Daily Temperatures
Use when: “top K”, “kth largest”, “merge k sorted”.
Min-heap of size K (keep largest K):
vector<int> topKLargest(const vector<int>& a, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
pq.push(x);
if ((int)pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); }
reverse(res.begin(), res.end());
return res;
}703. Kth Largest Element in a Stream (Easy)
1046. Last Stone Weight (Easy)
506. Relative Ranks (Easy)
1337. The K Weakest Rows in a Matrix (Easy)
703. Kth Largest Element in a Stream (Easy) (alternate practice: same pattern, great for repetition)
Use when: sorted search, lower/upper bound.
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == x) return mid;
else if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
return -1;- Binary Search — https://leetcode.com/problems/binary-search/
- Search Insert Position — https://leetcode.com/problems/search-insert-position/
- Sqrt(x) — https://leetcode.com/problems/sqrtx/
- First Bad Version — https://leetcode.com/problems/first-bad-version/
- Valid Perfect Square — https://leetcode.com/problems/valid-perfect-square/
Use when: “minimize maximum”, “maximize minimum”, partitioning.
bool can(const vector<int>& a, long long mid) {
// return true if answer <= mid is feasible
return true;
}
long long solve(const vector<int>& a) {
long long lo = 0, hi = 1e18; // set proper bounds
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (can(a, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}Key: can(mid) must be monotonic (true...true then false...false, or vice versa). 374. Guess Number Higher or Lower Link: https://leetcode.com/problems/guess-number-higher-or-lower/
-
Arranging Coins Link: https://leetcode.com/problems/arranging-coins/
-
Sqrt(x) Link: https://leetcode.com/problems/sqrtx/
-
Valid Perfect Square Link: https://leetcode.com/problems/valid-perfect-square/
-
Special Array With X Elements Greater Than or Equal X Link: https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/
Use when: shortest steps, level order traversal, grid distance.
int bfsGrid(vector<string>& g, int sr, int sc) {
int n = g.size(), m = g[0].size();
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int,int>> q;
dist[sr][sc] = 0;
q.push({sr, sc});
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
while (!q.empty()) {
auto [r,c] = q.front(); q.pop();
for (int k=0;k<4;k++){
int nr=r+dr[k], nc=c+dc[k];
if (nr<0||nr>=n||nc<0||nc>=m) continue;
if (g[nr][nc] == '#') continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr,nc});
}
}
return 0;
}LeetCode 733 — Flood Fill Link: https://leetcode.com/problems/flood-fill/ Why it fits: Classic grid BFS/DFS; use BFS from (sr, sc) to recolor all 4-directionally connected cells of the same original color. LeetCode 994 — Rotting Oranges Link: https://leetcode.com/problems/rotting-oranges/ Why it fits: Multi-source BFS on a grid; push all rotten oranges initially and expand level-by-level to compute minutes (shortest time). LeetCode 542 — 01 Matrix Link: https://leetcode.com/problems/01-matrix/ Why it fits: Multi-source BFS; start from all 0 cells and compute shortest distance to a 0 for every 1. LeetCode 1091 — Shortest Path in Binary Matrix Link: https://leetcode.com/problems/shortest-path-in-binary-matrix/ Why it fits: Straight shortest path in an unweighted grid (8 directions); BFS from (0,0) to (n-1,n-1). LeetCode 1926 — Nearest Exit from Entrance in Maze Link: https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/ Why it fits: BFS from the entrance; first time you reach any boundary cell (other than entrance) is the shortest exit distance.
Use when: tree properties: depth, sum, validate.
// LeetCode TreeNode is assumed
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}Copilot said: 1) 104. Maximum Depth of Binary Tree 104. Maximum Depth of Binary Tree Link: https://leetcode.com/problems/maximum-depth-of-binary-tree/ DFS recursion pattern: compute maxDepth(node) = 1 + max(depth(left), depth(right)).
-
Same Tree Link: https://leetcode.com/problems/same-tree/ DFS recursion pattern: recursively verify both nodes match and their subtrees match.
-
Symmetric Tree Link: https://leetcode.com/problems/symmetric-tree/ DFS recursion pattern: helper isMirror(a,b) comparing a.left with b.right and a.right with b.left.
-
Path Sum Link: https://leetcode.com/problems/path-sum/ DFS recursion pattern: carry remaining sum down the tree; check leaf condition.
-
Invert Binary Tree Link: https://leetcode.com/problems/invert-binary-tree/ DFS recursion pattern: recursively invert children, then swap left/right.
Use when: generate all combinations with pruning.
void dfs(int i, vector<int>& a, vector<int>& cur, vector<vector<int>>& out) {
if (i == (int)a.size()) { out.push_back(cur); return; }
dfs(i+1, a, cur, out); // skip
cur.push_back(a[i]);
dfs(i+1, a, cur, out); // take
cur.pop_back();
}#78 — Subsets https://leetcode.com/problems/subsets/
#46 — Permutations https://leetcode.com/problems/permutations/
#77 — Combinations https://leetcode.com/problems/combinations/
#784 — Letter Case Permutation https://leetcode.com/problems/letter-case-permutation/
#17 — Letter Combinations of a Phone Number https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Use when: best up to i, choose/skip (house robber, etc.)
int dpSolve(const vector<int>& a) {
int n = a.size();
vector<int> dp(n+1, 0);
// dp[i] = answer for first i elements
for (int i = 1; i <= n; i++) {
dp[i] = max(dp[i-1], dp[i-1] + a[i-1]); // placeholder transition
}
return dp[n];
}LeetCode #70 — Climbing Stairs https://leetcode.com/problems/climbing-stairs/
LeetCode #746 — Min Cost Climbing Stairs https://leetcode.com/problems/min-cost-climbing-stairs/
LeetCode #198 — House Robber https://leetcode.com/problems/house-robber/
LeetCode #1137 — N-th Tribonacci Number https://leetcode.com/problems/n-th-tribonacci-number/
LeetCode #392 — Is Subsequence https://leetcode.com/problems/is-subsequence/
Use when: components, dynamic connections.
struct DSU {
vector<int> p, r;
DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
bool unite(int a,int b){
a=find(a); b=find(b);
if(a==b) return false;
if(r[a]<r[b]) swap(a,b);
p[b]=a;
if(r[a]==r[b]) r[a]++;
return true;
}
};LeetCode 1971 — Find if Path Exists in Graph https://leetcode.com/problems/find-if-path-exists-in-graph/
LeetCode 547 — Number of Provinces https://leetcode.com/problems/number-of-provinces/
LeetCode 323 — Number of Connected Components in an Undirected Graph (Premium) https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
LeetCode 684 — Redundant Connection https://leetcode.com/problems/redundant-connection/
LeetCode 305 — Number of Islands II (Premium) https://leetcode.com/problems/number-of-islands-ii/