LeetCode C++ Cheat Sheet MAY

🧠 LeetCode C++ Cheat Sheet for Problem Solving

🧱 Basic Techniques in C++

Technique	When to Use	C++ STL/Approach
Two Pointers	Sorted arrays, find pair, reverse, remove duplicates	int i = 0, j = n - 1;
Sliding Window	Substrings, subarrays, max/min in window	unordered_map, set, manual window
Hash Map / Set	Frequency count, duplicates, lookups	unordered_map, unordered_set
Stack	Parentheses, next greater, monotonic problems	stack<int>
Binary Search	Sorted arrays, upper/lower bounds, min/max problem	binary_search(), lower_bound()
Backtracking	Permutations, subsets, N-queens	Recursive + vector, manual tracking
DP	Subproblems with overlapping states	vector<vector<int>> dp(n, vector<int>(m))
Union Find	Graph connectivity, components, cycle detection	Custom DSU class with find() and union()

---

🧮 Useful STL Containers

Container	Syntax Example
vector	vector<int> v; v.push_back(1);
unordered_map	unordered_map<int, int> mp; mp[key] = value;
unordered_set	unordered_set<int> st; st.insert(x);
stack	stack<int> s; s.push(x); s.top(); s.pop();
queue	queue<int> q; q.push(x); q.front(); q.pop();
priority_queue (max heap)	priority_queue<int> pq;
priority_queue (min heap)	priority_queue<int, vector<int>, greater<int>> pq;

---

🧩 Problem Pattern Shortcuts

Problem Type	C++ Trick
Two Sum	Use unordered_map<int, int> to store index
Longest Unique Substring	unordered_set<char> + two pointers
Valid Parentheses	stack<char>
Binary Tree Traversal	Recursive DFS or queue<TreeNode*> for BFS
Detect Graph Cycle	DFS + visited or DSU with path compression
Kth Largest Element	priority_queue<int, vector<int>, greater<int>> of size k
Merge Intervals	sort(intervals.begin(), intervals.end()), then merge
Subsets / Permutations	vector<int> path, backtracking with recursion

---

⏱ Time & Space Complexities

Operation	Time Complexity
Access in vector	O(1)
Insert in unordered_map	O(1) avg
Insert in set	O(log n)
sort()	O(n log n)
Binary Search	O(log n)
Heap insert/pop	O(log n)
Graph BFS/DFS	O(V + E)

---

🔧 Template Snippets (C++)

🔁 Sliding Window

int left = 0;
for (int right = 0; right < s.size(); ++right) {
    while (window_invalid_condition) {
        // shrink window
        left++;
    }
    // process window
}

🧭 DFS (recursive)

void dfs(TreeNode* root) {
    if (!root) return;
    dfs(root->left);
    dfs(root->right);
}

🔄 BFS

queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
    TreeNode* node = q.front(); q.pop();
    if (node->left) q.push(node->left);
    if (node->right) q.push(node->right);
}

🔁 Backtracking

void backtrack(vector<int>& path) {
    if (done_condition) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < choices.size(); ++i) {
        path.push_back(choices[i]);
        backtrack(path);
        path.pop_back();
    }
}

🧠 DP

vector<vector<int>> dp(n, vector<int>(m, 0));
// dp[i][j] = ...

🔗 Union Find

class DSU {
public:
    vector<int> parent;
    DSU(int n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};

---

🔄 Common Patterns to Practice (C++ Versions)

Pattern	Example Problem
Two Pointers	LeetCode 167. Two Sum II
Sliding Window	LeetCode 3. Longest Substring Without Repeating
Stack	LeetCode 20. Valid Parentheses
Hash Map	LeetCode 1. Two Sum, LeetCode 347. Top K Frequent Elements
BFS/DFS	LeetCode 102. Binary Tree Level Order, LeetCode 200. Number of Islands
Backtracking	LeetCode 46. Permutations, LeetCode 78. Subsets
DP	LeetCode 198. House Robber, LeetCode 70. Climbing Stairs
Heap	LeetCode 215. Kth Largest Element
Binary Search	LeetCode 33. Search in Rotated Sorted Array