LeetCode C++ Cheat Sheet June

🎯 Core Patterns & Representative Questions

1. Arrays & Hashing

• Two Sum – hash map → O(n)

• Contains Duplicate, Product of Array Except Self, Maximum Subarray (Kadane) (byby.dev, prepinsta.com)

2. Binary Search (Sorted & Answer Space)

• Search Insert Position, First Bad Version, Rotated Array Search, Find Minimum in Rotated Array, Peak Element, Split Array Largest Sum (kodnest.com)

3. Two Pointers & Sliding Window

• Container With Most Water, 3Sum, Minimum Window Substring, Longest Substring Without Repeating Characters (lets-code.co.in)

4. Stacks & Queues

• Valid Parentheses, Evaluate Reverse Polish Notation

5. Linked Lists

• Merge Two Sorted Lists, Reverse Linked List

6. Trees & Graphs

• Binary Tree Traversals, Number of Islands, Clone Graph, Course Schedule (lets-code.co.in)

7. Heaps & Priority Queues

• Merge k Sorted Lists, Top K Frequent Elements, Median from Data Stream (lets-code.co.in)

8. Dynamic Programming

• Climbing Stairs, Coin Change, Longest Increasing Subsequence, Word Break, Maximum Subarray

9. Backtracking

• Permutations, Combinations, Generate Parentheses, Word Search

10. Intervals

• Merge Intervals, Insert Interval, Minimum Number of Arrows to Burst Balloons

---

🚀 Why These?

• They cover ~75–150 essential problems seen across tech interviews (#Blind75 guides this list) (csmaven.com, lets-code.co.in).

• They're grouped by core techniques—key to pattern recognition during interviews.

• Repositories (GitHub “Top 150…” etc.) are organized the same way for efficient drill-down (github.com).

---

📚 How to Use This Cheat Sheet

1. Pattern Recognition: Read the problem prompt → map to a pattern above.

2. Recall Template: Use your stored C++ template (e.g., two-pointer or sliding window).

3. Implement & Discuss: Talk through:

   • Brute-force → point to inefficiencies.

   • Optimized solution → complexities, edge cases.

   • Time/Space tradeoffs.

4. Validate: Test on examples (e.g., “Two Sum” → [2,7,11,15], target=9, output = [0,1]).

---

🛠 Suggestion: Build Your Personal Toolbox

Create a .cpp file or repo with sections:

// Two Sum
vector<int> twoSum(...) { ... }
// Binary Search Template
int binarySearchTemplate(...) { ... }
// Sliding Window Template
int minWindow(...) { ... }
// ...

Populate it with solutions and sample inputs. Over time, this will become your go-to during interviews.

---

✅ Next Steps

• Start with “Blind 75” problems (github.com, udemy.com, leetcode.com, csmaven.com, wordsatease.com).

• Track progress through GitHub repos of “Top 150” (github.com).

• Focus on one pattern/week: implement 5 problems, track time and iteration steps.

• As you solve new problems, classify them by pattern and add to your toolbox.

 

---

🎯 Top 10 Core Algorithmic Patterns (with Purpose)

---

1. 🔁 Hashing / Hash Maps

Pattern: Use a map, unordered_map, or set to:

• Track frequencies

• Store visited elements

• Enable O(1) lookup

Used For:

• Constant-time search

• Duplicate detection

• Pair matching

• Frequency count

---

2. 🔍 Binary Search

Pattern: Divide the search space in half each time:

• On sorted arrays

• On “answer space” (e.g. min/max values)

Used For:

• Search in sorted arrays

• Finding first/last occurrence

• Min/max problem solving (searching over results, not array)

---

3. 🔄 Two Pointers

Pattern: Use two pointers to scan array:

• Either moving toward each other or in parallel

Used For:

• Finding pairs

• Sorting/merging arrays

• Removing duplicates

• Palindrome checks

---

4. 🚪 Sliding Window

Pattern: Expand + shrink a window over an array or string:

• Typically uses two pointers with conditions

Used For:

• Substring or subarray problems

• Longest/shortest with a constraint

• Minimum/maximum window containing elements

---

5. 🧱 Stack-Based Processing

Pattern: Use LIFO data structure to:

• Track state

• Handle nested operations

• Reverse sequences

Used For:

• Matching parentheses/brackets

• Undo operations

• Monotonic stacks (next greater/smaller)

---

6. 🔗 Linked List Manipulation

Pattern: Use pointer manipulation to:

• Traverse

• Reverse

• Merge

• Detect cycles

Used For:

• In-place list operations

• Pointer movement control

• Fast/slow pointer tricks

---

7. 🌳 Graph & Tree Traversals (DFS/BFS)

Pattern:

• Use recursion (DFS) or queue (BFS)

• Traverse nodes, track visited, handle recursion stack

Used For:

• Pathfinding

• Island counting

• Tree recursion

• Cycle detection

---

8. 🥇 Greedy Algorithms

Pattern: Make local optimal choice at each step assuming it leads to global optimum

Used For:

• Interval scheduling

• Minimizing operations

• Resource allocation

---

9. 💡 Dynamic Programming

Pattern: Break down problems into overlapping subproblems, memoize results

Used For:

• Optimal subsequences (LIS, LCS)

• Count ways (staircase, coin change)

• Subarray/subset sum problems

---

10. 🧩 Backtracking

Pattern: Recursively build candidates and backtrack upon invalid state

Used For:

• All combinations / permutations

• Decision trees

• Constraint satisfaction (sudoku, N-Queens)

---

✅ Bonus: Intervals & Sorting

Pattern: Sort by start or end time and:

• Merge

• Select non-overlapping intervals

• Sweep line algorithms

Used For:

• Time-based scheduling

• Range merging

• Event processing

---

 

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