DSA PATTERNS

Complete C++ Notes · Tricks · Mind Maps

Interview Preparation · All Patterns · Company Focus

18 30+ 8 50+
Patterns C++ Templates Mind Maps Tricks

2nd Year
Focus: Array, HashMap, 2-Pointers

3rd Year
Focus: DFS/BFS, DP, Backtracking

4th Year
Focus: Topo Sort, Union-Find, Hybrids

Generated for interview preparation · Covers Google, Meta, Amazon, Microsoft, Cisco, Adobe & more

DSA Patterns · C++ Notes · Interview Prep Page 1

 TABLE OF CONTENTS
Quick navigation guide

1 Sliding Window – Fixed & Variable Sec 1

2 Two Pointers – Convergence & In-Place Sec 2

3 Fast & Slow Pointers (Floyd's) Sec 3

4 In-Place Reversal of Linked List Sec 4

5 LinkedList + HashMap (Clone) Sec 5

6 Monotonic Stack – Decreasing & Increasing Sec 6

7 Stack – String & Expression Parsing Sec 7

8 DFS – Trees & Graphs Sec 8

9 BFS – Trees, Graphs & Multi-Source Sec 9

10 Topological Sort (Kahn's) Sec 10

11 Union-Find (DSU) Sec 11

12 Binary Search – Classic & On Answer Sec 12

13 Merge Intervals Sec 13

14 1D Dynamic Programming (Kadane's) Sec 14

15 2D Dynamic Programming (LCS) Sec 15

16 State-Machine DP (Stock Problems) Sec 16

17 Backtracking Sec 17

18 Year-wise Strategy + Complexity Sheet Sec 18

DSA Patterns · C++ Notes · Interview Prep Page 2

 SEC 1 · SLIDING WINDOW
Fixed window + Variable window — O(n) linear scan

Max/Min Track

Prefix Sum Freq HashMap

Sliding Window

Two Indices Variable Size

Fixed Size k

1A · Fixed Window — Template

TIME: O(n) SPACE: O(1)

1 // Fixed Window of size k

2 int fixedWindow(vector<int>& arr, int k) {
3 int n = [Link]();
4 int windowSum = 0, maxSum = 0;
5 // Build first window
6 for (int i = 0; i < k; i++)
7 windowSum += arr[i];
8 maxSum = windowSum;
9 // Slide: add new, remove outgoing
10 for (int i = k; i < n; i++) {
11 windowSum += arr[i]; // add incoming
12 windowSum -= arr[i - k]; // remove outgoing
13 maxSum = max(maxSum, windowSum);
14 }
15 return maxSum;
16 }

1B · Variable Window — Longest Substring No Repeat

TIME: O(n) SPACE: O(k) k=distinct chars

DSA Patterns · C++ Notes · Interview Prep Page 3

 1 int lengthOfLongestSubstring(string s) {
2 unordered_map<char, int> freq;
3 int left = 0, maxLen = 0;
4 for (int right = 0; right < [Link](); right++) {
5 freq[s[right]]++; // expand right
6 // Shrink left while constraint violated
7 while (freq[s[right]] > 1) {
8 freq[s[left]]--;
9 left++;
10 }
11 maxLen = max(maxLen, right - left + 1);
12 }
13 return maxLen;
14 }

1C · Variable Window — Max Consecutive Ones III (flip k zeros)

1 int longestOnes(vector<int>& nums, int k) {

2 int left = 0, zeros = 0, maxLen = 0;
3 for (int right = 0; right < [Link](); right++) {
4 if (nums[right] == 0) zeros++;
5 while (zeros > k) { // too many zeros -> shrink
6 if (nums[left] == 0) zeros--;
7 left++;
8 }
9 maxLen = max(maxLen, right - left + 1);
10 }
11 return maxLen;
12 }

SLIDING WINDOW TRICKS

Fixed: windowSum += arr[right] - arr[right-k] (one-liner slide)

Variable: while(violated) shrink left | always update ans AFTER shrink
Trigger words: 'contiguous subarray', 'substring', 'at most k', 'no repeating'
Use HashMap for char frequency; use int counter for simpler constraints
Window length formula: right - left + 1 (inclusive both ends)
For 'exactly k' problems: f(exactly k) = f(at most k) - f(at most k-1)

DSA Patterns · C++ Notes · Interview Prep Page 4

 SEC 2 · TWO POINTERS
Convergence (sorted) + In-Place (overwrite) — O(n) O(1)

Pair Sum

Remove Duplicates Sorted Input

Two Pointers

3-Sum In-Place Write

Left+Right Converge

2A · Convergence — Container With Most Water

TIME: O(n) SPACE: O(1)

1 int maxArea(vector<int>& h) {
2 int left = 0, right = [Link]()-1, res = 0;
3 while (left < right) {
4 int area = min(h[left], h[right]) * (right - left);
5 res = max(res, area);
6 // Move the shorter wall inward (greedy)
7 if (h[left] < h[right]) left++;
8 else right--;
9 }
10 return res;
11 }

2B · In-Place — Remove Element

TIME: O(n) SPACE: O(1)

1 int removeElement(vector<int>& nums, int val) {

2 int slow = 0; // write head
3 for (int fast = 0; fast < [Link](); fast++) {
4 if (nums[fast] != val) { // valid element
5 nums[slow] = nums[fast];
6 slow++; // advance write head
7 }
8 }
9 return slow; // new length
10 }

DSA Patterns · C++ Notes · Interview Prep Page 5

 2C · 3Sum (Two Pointers after sort)

TIME: O(n^2) SPACE: O(1)

1 vector<vector<int>> threeSum(vector<int>& nums) {

2 sort([Link](), [Link]());
3 vector<vector<int>> res;
4 for (int i = 0; i < [Link]()-2; i++) {
5 if (i > 0 && nums[i] == nums[i-1]) continue; // skip dup
6 int l = i+1, r = [Link]()-1;
7 while (l < r) {
8 int s = nums[i] + nums[l] + nums[r];
9 if (s == 0) { res.push_back({nums[i],nums[l],nums[r]}); l++; r--; }
10 else if (s < 0) l++;
11 else r--;
12 }
13 }
14 return res;
15 }

TWO POINTER TRICKS

Convergence REQUIRES sorted input — always sort first if not sorted

Move the side that limits the answer: shorter bar in container problem
In-place: slow = write head, fast = read head — slow advances only on valid
Skip duplicates: if nums[i] == nums[i-1] continue (after sorting)
Two-sum in sorted array: l++ if sum too small, r-- if sum too large
For cycle detection use fast(+2) and slow(+1) — Floyd's variant

DSA Patterns · C++ Notes · Interview Prep Page 6

 SEC 3 · FAST & SLOW POINTERS (FLOYD'S)
Cycle detection in O(n) O(1) — Linked lists & arrays

3A · Detect Cycle in Linked List

TIME: O(n) SPACE: O(1)

1 struct ListNode { int val; ListNode* next; };

2
3 bool hasCycle(ListNode* head) {
4 ListNode* slow = head;
5 ListNode* fast = head;
6 while (fast && fast->next) {
7 slow = slow->next; // move 1 step
8 fast = fast->next->next; // move 2 steps
9 if (slow == fast) return true; // cycle!
10 }
11 return false;
12 }

3B · Find Cycle Entry Point

1 ListNode* detectCycle(ListNode* head) {

2 ListNode* slow = head, *fast = head;
3 while (fast && fast->next) {
4 slow = slow->next;
5 fast = fast->next->next;
6 if (slow == fast) {
7 // Reset one pointer to head
8 ListNode* ptr = head;
9 while (ptr != slow) { // both move 1 step
10 ptr = ptr->next;
11 slow = slow->next;
12 }
13 return ptr; // cycle entry
14 }
15 }
16 return nullptr;
17 }

3C · Find Middle of Linked List

DSA Patterns · C++ Notes · Interview Prep Page 7

 1 ListNode* middleNode(ListNode* head) {
2 ListNode* slow = head, *fast = head;
3 while (fast && fast->next) {
4 slow = slow->next;
5 fast = fast->next->next;
6 }
7 return slow; // slow is at middle when fast reaches end
8 }

FAST & SLOW TRICKS

Meet condition: slow == fast (they WILL meet if cycle exists)

Cycle entry: reset one ptr to head, move both 1-step until equal
Middle node: when fast reaches end, slow is at middle
Palindrome list: find mid, reverse 2nd half, compare with 1st half
Find duplicate (Floyd): treat array as linked list via index as pointer
Always check: while(fast && fast->next) to avoid null dereference

DSA Patterns · C++ Notes · Interview Prep Page 8

 SEC 4 · IN-PLACE REVERSAL OF LINKED LIST
Reverse entire list / k-groups — O(n) O(1)

4A · Reverse Entire Linked List

TIME: O(n) SPACE: O(1)

1 ListNode* reverseList(ListNode* head) {

2 ListNode* prev = nullptr;
3 ListNode* curr = head;
4 while (curr) {
5 ListNode* next = curr->next; // save next
6 curr->next = prev; // reverse pointer
7 prev = curr; // advance prev
8 curr = next; // advance curr
9 }
10 return prev; // prev is new head
11 }

4B · Reverse Nodes in k-Group

TIME: O(n) SPACE: O(n/k) recursion stack

1 ListNode* reverseKGroup(ListNode* head, int k) {

2 ListNode* curr = head;
3 int count = 0;
4 while (curr && count < k) { curr = curr->next; count++; }
5 if (count < k) return head; // not enough nodes
6 // Reverse k nodes
7 ListNode* prev = nullptr, *node = head;
8 for (int i = 0; i < k; i++) {
9 ListNode* nxt = node->next;
10 node->next = prev;
11 prev = node;
12 node = nxt;
13 }
14 // head is now tail of reversed group
15 head->next = reverseKGroup(node, k);
16 return prev; // prev is new head of group
17 }

DSA Patterns · C++ Notes · Interview Prep Page 9

 REVERSAL TRICKS

Three-pointer pattern: prev=null, curr=head, next=curr->next

After loop: prev is the new head (last processed node)
Reverse sublist [m,n]: traverse to (m-1)th node, reverse n-m+1 nodes
k-group: check if k nodes remain before reversing, recurse on rest
Palindrome: reverse 2nd half in-place, compare, then reverse back
Store dummy->next = head to handle edge case of reversing from node 1

DSA Patterns · C++ Notes · Interview Prep Page 10

 SEC 5 · LINKEDLIST + HASHMAP
Deep clone with random pointers — O(n) two-pass

5A · Copy List with Random Pointer

TIME: O(n) SPACE: O(n)

1 class Node { public: int val; Node* next; Node* random; };

2
3 Node* copyRandomList(Node* head) {
4 if (!head) return nullptr;
5 unordered_map<Node*, Node*> mp; // old -> new
6 // Pass 1: create all new nodes
7 Node* curr = head;
8 while (curr) {
9 mp[curr] = new Node(curr->val);
10 curr = curr->next;
11 }
12 // Pass 2: wire next and random pointers
13 curr = head;
14 while (curr) {
15 if (curr->next) mp[curr]->next = mp[curr->next];
16 if (curr->random) mp[curr]->random = mp[curr->random];
17 curr = curr->next;
18 }
19 return mp[head];
20 }

5B · LRU Cache (HashMap + Doubly Linked List)

TIME: O(1) per op SPACE: O(capacity)

DSA Patterns · C++ Notes · Interview Prep Page 11

 1 class LRUCache {
2 int cap;
3 list<pair<int,int>> cache; // {key,val} MRU at front
4 unordered_map<int, list<pair<int,int>>::iterator> mp;
5 public:
6 LRUCache(int cap) : cap(cap) {}
7 int get(int key) {
8 if () return -1;
9 [Link]([Link](), cache, mp[key]); // move to front
10 return mp[key]->second;
11 }
12 void put(int key, int val) {
13 if ([Link](key)) [Link](mp[key]);
14 cache.push_front({key, val});
15 mp[key] = [Link]();
16 if ([Link]() > cap) {
17 [Link]([Link]().first);
18 cache.pop_back(); // evict LRU
19 }
20 }
21 };

HASHMAP + LIST TRICKS

Two-pass clone: Pass1=create nodes, Pass2=wire pointers (never one-pass for random)
LRU: list<pair<int,int>> + unordered_map to iterator — O(1) splice
list::splice moves element to front without reallocation
Always check [Link](key) before accessing — avoid undefined behavior
LFU variant: two hashmaps (key->freq, freq->list) + min_freq tracker
Clone graph: same pattern — BFS/DFS + HashMap old->new node

DSA Patterns · C++ Notes · Interview Prep Page 12

 SEC 6 · MONOTONIC STACK
Next Greater / Largest Rectangle — O(n) amortized push+pop

Histogram Area

Stock Span NGE / NLE

Monotonic Stack

Trap Water Increasing Stack

Decreasing Stack

6A · Decreasing Stack — Daily Temperatures (Next Greater)

TIME: O(n) SPACE: O(n)

1 // Stack stores INDICES, not values

2 vector<int> dailyTemperatures(vector<int>& T) {
3 int n = [Link]();
4 vector<int> res(n, 0);
5 stack<int> st; // decreasing stack (of indices)
6 for (int i = 0; i < n; i++) {
7 // Pop while current temp > stack top temp
8 while (![Link]() && T[i] > T[[Link]()]) {
9 res[[Link]()] = i - [Link](); // days to wait
10 [Link]();
11 }
12 [Link](i);
13 }
14 return res;
15 }

6B · Increasing Stack — Largest Rectangle in Histogram

TIME: O(n) SPACE: O(n)

DSA Patterns · C++ Notes · Interview Prep Page 13

 1 int largestRectangleArea(vector<int>& h) {
2 stack<int> st; // increasing stack (indices)
3 int maxArea = 0;
4 h.push_back(0); // sentinel to flush remaining bars
5 for (int i = 0; i < [Link](); i++) {
6 while (![Link]() && h[i] < h[[Link]()]) {
7 int height = h[[Link]()]; [Link]();
8 int width = [Link]() ? i : i - [Link]() - 1;
9 maxArea = max(maxArea, height * width);
10 }
11 [Link](i);
12 }
13 return maxArea;
14 }

MONOTONIC STACK TRICKS

Decreasing stack: pop when arr[i] > arr[top] → solves 'Next Greater'
Increasing stack: pop when arr[i] < arr[top] → solves area/span problems
Store INDICES not values — you need position to compute width/distance
Append sentinel (0 or INT_MAX) to flush all remaining elements at end
Width formula for histogram: [Link]() ? i : i - [Link]() - 1
Trapping Rain Water: also solved with decreasing monotonic stack
Each element is pushed and popped at most once → O(n) total

DSA Patterns · C++ Notes · Interview Prep Page 14

 SEC 7 · STACK — STRINGS & EXPRESSIONS
Adjacent duplicates, balanced parens, calculator — LIFO

7A · Remove All Adjacent Duplicates

TIME: O(n) SPACE: O(n)

1 string removeDuplicates(string s) {
2 string stk; // use string as stack (efficient)
3 for (char c : s) {
4 if (![Link]() && [Link]() == c)
5 stk.pop_back(); // cancel adjacent pair
6 else
7 stk.push_back(c);
8 }
9 return stk;
10 }

7B · Basic Calculator (with + - and parentheses)

TIME: O(n) SPACE: O(n)

1 int calculate(string s) {
2 stack<int> st; // stores result and sign before '('
3 int result = 0, num = 0, sign = 1;
4 for (char c : s) {
5 if (isdigit(c)) {
6 num = num * 10 + (c - '0');
7 } else if (c == '+') { result += sign * num; num=0; sign=1; }
8 else if (c == '-') { result += sign * num; num=0; sign=-1; }
9 else if (c == '(') {
10 [Link](result); [Link](sign); // save context
11 result = 0; sign = 1;
12 } else if (c == ')') {
13 result += sign * num; num = 0;
14 result *= [Link](); [Link](); // multiply by sign before '('
15 result += [Link](); [Link](); // add result before '('
16 }
17 }
18 return result + sign * num;
19 }

DSA Patterns · C++ Notes · Interview Prep Page 15

 STACK / EXPRESSION TRICKS

Use string as stack: push_back / pop_back faster than stack<char>

Calculator: push (result, sign) on '(' — restore on ')'
Valid parentheses: push open brackets, on close check top matches
Decode string '3[ab]': push count and built string on '[', pop on ']'
Simplify path: split by '/', push dirs, skip '.' and handle '..' with pop
sign variable stores +1 or -1; multiplied with number before adding

DSA Patterns · C++ Notes · Interview Prep Page 16

 SEC 8 · DEPTH-FIRST SEARCH (DFS)
Trees + Graphs — recursive/iterative — O(V+E)

Visited Set (Graph)

Path Tracking Postorder L-R-Root

DFS

Subtree Check Inorder L-Root-R

Preorder Root-L-R

8A · DFS Template — Graph

TIME: O(V+E) SPACE: O(V) visited + O(h) stack

1 // adjacency list graph

2 vector<vector<int>> adj;
3 vector<bool> visited;
4
5 void dfs(int node) {
6 visited[node] = true;
7 for (int neighbor : adj[node]) {
8 if (!visited[neighbor])
9 dfs(neighbor);
10 }
11 }
12
13 // Count connected components
14 int countComponents(int n, vector<vector<int>>& edges) {
15 [Link](n, {}); [Link](n, false);
16 for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
17 int components = 0;
18 for (int i = 0; i < n; i++)
19 if (!visited[i]) { dfs(i); components++; }
20 return components;
21 }

8B · DFS — Subtree of Another Tree

DSA Patterns · C++ Notes · Interview Prep Page 17

 1 struct TreeNode { int val; TreeNode* left; TreeNode* right; };
2
3 bool isSameTree(TreeNode* s, TreeNode* t) {
4 if (!s && !t) return true;
5 if (!s || !t || s->val != t->val) return false;
6 return isSameTree(s->left,t->left) && isSameTree(s->right,t->right);
7 }
8
9 bool isSubtree(TreeNode* root, TreeNode* sub) {
10 if (!root) return false;
11 if (isSameTree(root, sub)) return true;
12 return isSubtree(root->left, sub) || isSubtree(root->right, sub);
13 }

8C · DFS — All Paths in Grid (Pacific Atlantic)

1 void dfs(vector<vector<int>>& h, vector<vector<bool>>& vis,

2 int r, int c, int prev) {
3 if (r<0||c<0||r>=[Link]()||c>=h[0].size()) return;
4 if (vis[r][c] || h[r][c] < prev) return; // can't flow uphill
5 vis[r][c] = true;
6 for (auto [dr,dc] : vector<pair<int,int>>{{0,1},{0,-1},{1,0},{-1,0}})
7 dfs(h, vis, r+dr, c+dc, h[r][c]);
8 }

DFS TRICKS

Always mark visited BEFORE recursing to prevent infinite loops in graphs

Preorder=process before children, Postorder=process after (bottom-up height)
Iterative DFS: use explicit stack<int>, push neighbors in reverse order
Grid DFS: 4 directions = {{0,1},{0,-1},{1,0},{-1,0}} — store as array
Path tracking: push to path before recurse, pop after (backtrack)
Serialize tree: preorder with '#' for null — unique representation

DSA Patterns · C++ Notes · Interview Prep Page 18

 SEC 9 · BREADTH-FIRST SEARCH (BFS)
Level-order + Shortest Path + Multi-Source — O(V+E)

9A · BFS Template — Tree Level Order

TIME: O(n) SPACE: O(w) w=max level width

1 vector<vector<int>> levelOrder(TreeNode* root) {

2 if (!root) return {};
3 vector<vector<int>> res;
4 queue<TreeNode*> q;
5 [Link](root);
6 while (![Link]()) {
7 int levelSize = [Link](); // snapshot current level
8 vector<int> level;
9 for (int i = 0; i < levelSize; i++) {
10 TreeNode* node = [Link](); [Link]();
11 level.push_back(node->val);
12 if (node->left) [Link](node->left);
13 if (node->right) [Link](node->right);
14 }
15 res.push_back(level);
16 }
17 return res;
18 }

9B · BFS Shortest Path — Snakes and Ladders

DSA Patterns · C++ Notes · Interview Prep Page 19

 1 int snakesAndLadders(vector<vector<int>>& board) {
2 int n = [Link](), steps = 0;
3 auto getPos = [&](int s) -> pair<int,int> {
4 int row = (s-1)/n, col = (s-1)%n;
5 if (row%2==1) col = n-1-col; // boustrophedon
6 return {n-1-row, col};
7 };
8 vector<bool> vis(n*n+1, false);
9 queue<int> q; [Link](1); vis[1]=true;
10 while (![Link]()) {
11 for (int sz=[Link](); sz>0; sz--) {
12 int cur = [Link](); [Link]();
13 if (cur == n*n) return steps;
14 for (int d=1; d<=6 && cur+d<=n*n; d++) {
15 auto [r,c] = getPos(cur+d);
16 int next = board[r][c]==-1 ? cur+d : board[r][c];
17 if (!vis[next]) { vis[next]=true; [Link](next); }
18 }
19 }
20 steps++;
21 }
22 return -1;
23 }

9C · Multi-Source BFS — 01 Matrix (distance to nearest 0)

1 vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {

2 int m=[Link](), n=mat[0].size();
3 vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
4 queue<pair<int,int>> q;
5 // Enqueue ALL 0-cells simultaneously
6 for (int i=0;i<m;i++) for(int j=0;j<n;j++)
7 if (mat[i][j]==0) { dist[i][j]=0; [Link]({i,j}); }
8 int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
9 while (![Link]()) {
10 auto [r,c] = [Link](); [Link]();
11 for (auto& d : dirs) {
12 int nr=r+d[0], nc=c+d[1];
13 if (nr>=0&&nr<m&&nc>=0&&nc<n&&dist[nr][nc]==INT_MAX) {
14 dist[nr][nc] = dist[r][c]+1;
15 [Link]({nr,nc});
16 }
17 }
18 }
19 return dist;
20 }

DSA Patterns · C++ Notes · Interview Prep Page 20

 BFS TRICKS

Level tracking: snapshot [Link]() BEFORE inner loop (not during)

Shortest path: BFS guarantees shortest in UNWEIGHTED graph (not DFS!)
Multi-source: add ALL sources to queue before starting BFS
Visited array: mark WHEN ENQUEUING not when dequeuing (prevent duplicates)
Grid BFS: flatten 2D to 1D index — cell = r*cols + c
Word ladder: BFS on string states, each char change = one edge
Bidirectional BFS: start from both ends, meet in middle — sqrt(n) speedup

DSA Patterns · C++ Notes · Interview Prep Page 21

 SEC 10 · TOPOLOGICAL SORT (KAHN'S BFS)
DAG ordering with dependencies — O(V+E)

10A · Course Schedule (Cycle Detection)

TIME: O(V+E) SPACE: O(V+E)

1 bool canFinish(int n, vector<vector<int>>& prereqs) {

2 vector<int> indegree(n, 0);
3 vector<vector<int>> adj(n);
4 for (auto& p : prereqs) {
5 adj[p[1]].push_back(p[0]);
6 indegree[p[0]]++;
7 }
8 queue<int> q;
9 for (int i=0; i<n; i++)
10 if (indegree[i]==0) [Link](i); // all zero-indegree nodes
11 int processed = 0;
12 while (![Link]()) {
13 int node = [Link](); [Link](); processed++;
14 for (int nb : adj[node]) {
15 if (--indegree[nb] == 0) [Link](nb); // neighbor freed
16 }
17 }
18 return processed == n; // if < n, cycle exists
19 }

10B · Course Schedule II (Return Order)

1 vector<int> findOrder(int n, vector<vector<int>>& prereqs) {

2 vector<int> indegree(n,0);
3 vector<vector<int>> adj(n);
4 for (auto& p : prereqs) { adj[p[1]].push_back(p[0]); indegree[p[0]]++; }
5 queue<int> q;
6 for (int i=0;i<n;i++) if(indegree[i]==0) [Link](i);
7 vector<int> order;
8 while (![Link]()) {
9 int node = [Link](); [Link]();
10 order.push_back(node);
11 for (int nb : adj[node])
12 if (--indegree[nb]==0) [Link](nb);
13 }
14 return [Link]()==n ? order : vector<int>{};
15 }

DSA Patterns · C++ Notes · Interview Prep Page 22

 TOPOLOGICAL SORT TRICKS

Cycle detection: if processed != n after BFS, there is a cycle in the DAG

indegree[v]++ for each edge u->v; start BFS with all zero-indegree nodes
DFS variant: finish time ordering — push to result on DFS return
Alien dictionary: build graph from consecutive word pair differences
Task scheduling (min time): use priority queue variant (longest job first)
Parallel courses: BFS level gives minimum semesters needed

DSA Patterns · C++ Notes · Interview Prep Page 23

 SEC 11 · UNION-FIND (DISJOINT SET UNION)
Path compression + Union by rank — O(α(n)) per op

11A · DSU Full Template

TIME: O(alpha(n)) ~SPACE:

O(1) O(n)

1 class DSU {
2 vector<int> parent, rank_;
3 int components;
4 public:
5 DSU(int n) : parent(n), rank_(n,0), components(n) {
6 iota([Link](), [Link](), 0); // parent[i] = i
7 }
8 int find(int x) { // path compression
9 if (parent[x] != x)
10 parent[x] = find(parent[x]); // flatten tree
11 return parent[x];
12 }
13 bool unite(int x, int y) { // union by rank
14 int px=find(x), py=find(y);
15 if (px==py) return false; // already connected
16 if (rank_[px] < rank_[py]) swap(px, py);
17 parent[py] = px;
18 if (rank_[px]==rank_[py]) rank_[px]++;
19 components--;
20 return true;
21 }
22 int count() { return components; }
23 };

11B · Number of Islands using DSU

1 int numIslands(vector<vector<char>>& grid) {

2 int m=[Link](), n=grid[0].size();
3 DSU dsu(m*n);
4 int water = 0;
5 for (int i=0;i<m;i++) for(int j=0;j<n;j++) {
6 if (grid[i][j]=='0') { water++; continue; }
7 if (i>0 && grid[i-1][j]=='1') [Link](i*n+j,(i-1)*n+j);
8 if (j>0 && grid[i][j-1]=='1') [Link](i*n+j,i*n+j-1);
9 }
10 return [Link]() - water;
11 }

DSA Patterns · C++ Notes · Interview Prep Page 24

 UNION-FIND TRICKS

Path compression: parent[x] = find(parent[x]) — recursive flattening

Union by rank: attach smaller tree under larger to keep height O(log n)
Initialize: iota([Link](), [Link](), 0) for parent[i]=i
Detect cycle in undirected graph: unite returns false if already connected
Grid: cell (r,c) → 1D index = r*cols + c
Accounts merge: union emails by account, group by find(representative)
Redundant connection: first edge where find(u)==find(v) is redundant

DSA Patterns · C++ Notes · Interview Prep Page 25

 SEC 12 · BINARY SEARCH
Classic + On Answer Space + 2D Matrix — O(log n)

Monotone Predicate

Left/Right Boundary 2D Matrix

Binary Search

Rotated Array On Answer Space

Classic Array

12A · Classic Binary Search + Boundaries

TIME: O(log n) SPACE: O(1)

1 // Standard: find exact target

2 int binarySearch(vector<int>& arr, int target) {
3 int lo=0, hi=[Link]()-1;
4 while (lo <= hi) {
5 int mid = lo + (hi-lo)/2; // avoid overflow!
6 if (arr[mid]==target) return mid;
7 else if (arr[mid]<target) lo=mid+1;
8 else hi=mid-1;
9 }
10 return -1;
11 }
12
13 // Left boundary: first position >= target (lower_bound)
14 int lowerBound(vector<int>& arr, int target) {
15 int lo=0, hi=[Link]();
16 while (lo<hi) {
17 int mid=lo+(hi-lo)/2;
18 if (arr[mid]<target) lo=mid+1;
19 else hi=mid; // mid could be answer
20 }
21 return lo;
22 }

12B · Binary Search on Answer — Koko Eating Bananas

DSA Patterns · C++ Notes · Interview Prep Page 26

 1 // Can Koko eat all piles in h hours at speed k?
2 bool canEat(vector<int>& piles, long long k, int h) {
3 long long hours = 0;
4 for (int p : piles) hours += (p + k - 1) / k; // ceil(p/k)
5 return hours <= h;
6 }
7
8 int minEatingSpeed(vector<int>& piles, int h) {
9 int lo=1, hi=*max_element([Link](),[Link]());
10 while (lo<hi) {
11 int mid=lo+(hi-lo)/2;
12 if (canEat(piles, mid, h)) hi=mid; // mid works, try smaller
13 else lo=mid+1; // mid too slow
14 }
15 return lo;
16 }

12C · Search in 2D Matrix

1 bool searchMatrix(vector<vector<int>>& matrix, int target) {

2 int m=[Link](), n=matrix[0].size();
3 int lo=0, hi=m*n-1;
4 while (lo<=hi) {
5 int mid=lo+(hi-lo)/2;
6 int val = matrix[mid/n][mid%n]; // 1D->2D mapping
7 if (val==target) return true;
8 else if (val<target) lo=mid+1;
9 else hi=mid-1;
10 }
11 return false;
12 }

BINARY SEARCH TRICKS

mid = lo + (hi-lo)/2 — NEVER (lo+hi)/2 (integer overflow for large arrays)

Answer space BS: if predicate(mid) true -> hi=mid, else -> lo=mid+1
Left boundary: while(lo<hi), on match do hi=mid (not hi=mid-1)
Right boundary: while(lo<hi), on match do lo=mid+1, return lo-1
2D to 1D: row = mid/cols, col = mid%cols
Rotated sorted array: check which half is monotone, search there
Floating point BS: iterate fixed 100 times instead of lo<hi

DSA Patterns · C++ Notes · Interview Prep Page 27

 SEC 13 · MERGE INTERVALS
Sort + greedy merge — O(n log n) sort, O(n) merge

13A · Merge Intervals

TIME: O(n log n) SPACE: O(n)

1 vector<vector<int>> merge(vector<vector<int>>& intervals) {

2 sort([Link](), [Link]()); // sort by start
3 vector<vector<int>> res;
4 for (auto& iv : intervals) {
5 if ([Link]() || [Link]()[1] < iv[0])
6 res.push_back(iv); // no overlap, add new
7 else
8 [Link]()[1] = max([Link]()[1], iv[1]); // extend
9 }
10 return res;
11 }

13B · Insert Interval

1 vector<vector<int>> insert(vector<vector<int>>& ivs, vector<int>& newIv) {

2 vector<vector<int>> res;
3 int i=0, n=[Link]();
4 // Add all intervals ending before newIv starts
5 while (i<n && ivs[i][1] < newIv[0]) res.push_back(ivs[i++]);
6 // Merge all overlapping intervals
7 while (i<n && ivs[i][0] <= newIv[1]) {
8 newIv[0] = min(newIv[0], ivs[i][0]);
9 newIv[1] = max(newIv[1], ivs[i][1]);
10 i++;
11 }
12 res.push_back(newIv);
13 // Add remaining
14 while (i<n) res.push_back(ivs[i++]);
15 return res;
16 }

INTERVAL TRICKS

Always sort by START time first — enables single-pass O(n) merge

Overlap condition: [Link] <= [Link] (not strict less than)
Merge: new_end = max([Link], [Link]) — prev may completely contain curr
Meeting rooms II (min rooms): sort by start, use min-heap of end times
Non-overlapping intervals (min remove): sort by END, greedy keep non-overlap
Interval scheduling: sort by end time → greedy select non-overlapping → O(n log n)

DSA Patterns · C++ Notes · Interview Prep Page 28

 SEC 14 · 1D DYNAMIC PROGRAMMING
Kadane's + House Robber + Coin Change — O(n)

Climbing Stairs

Jump Game Coin Change

1D DP

Decode Ways House Robber

Kadane's Max Sub

14A · Kadane's Algorithm — Maximum Subarray

TIME: O(n) SPACE: O(1)

1 int maxSubArray(vector<int>& nums) {

2 int curr = nums[0], best = nums[0];
3 for (int i=1; i<[Link](); i++) {
4 // Either extend current subarray or start fresh
5 curr = max(nums[i], curr + nums[i]);
6 best = max(best, curr);
7 }
8 return best;
9 }
10
11 // Variant: return subarray indices
12 pair<int,int> maxSubArrayIdx(vector<int>& nums) {
13 int curr=nums[0], best=nums[0], start=0, s=0, e=0;
14 for (int i=1;i<[Link]();i++) {
15 if (curr+nums[i] < nums[i]) { curr=nums[i]; start=i; }
16 else curr += nums[i];
17 if (curr > best) { best=curr; s=start; e=i; }
18 }
19 return {s, e};
20 }

14B · House Robber (non-adjacent)

DSA Patterns · C++ Notes · Interview Prep Page 29

 1 int rob(vector<int>& nums) {
2 int prev2=0, prev1=0;
3 for (int n : nums) {
4 int curr = max(prev1, prev2 + n); // rob or skip
5 prev2 = prev1;
6 prev1 = curr;
7 }
8 return prev1;
9 }

14C · Coin Change (min coins)

TIME: O(n*amount) SPACE: O(amount)

1 int coinChange(vector<int>& coins, int amount) {

2 vector<int> dp(amount+1, INT_MAX);
3 dp[0] = 0; // base case
4 for (int i=1; i<=amount; i++) {
5 for (int c : coins) {
6 if (c<=i && dp[i-c]!=INT_MAX)
7 dp[i] = min(dp[i], dp[i-c]+1);
8 }
9 }
10 return dp[amount]==INT_MAX ? -1 : dp[amount];
11 }

1D DP TRICKS

Kadane's: curr = max(num, curr+num) — 'start fresh or extend'

Optimize space: most 1D DP only needs prev1 and prev2 (O(1) space)
Bottom-up vs Top-down: bottom-up avoids recursion stack, usually faster
Coin change (count ways): dp[i] += dp[i-coin] for all coins
Jump game: maintain maxReach = max(maxReach, i + nums[i])
Decode ways: dp[i] = dp[i-1] (1-digit) + dp[i-2] (2-digit if valid)

DSA Patterns · C++ Notes · Interview Prep Page 30

 SEC 15 · 2D DYNAMIC PROGRAMMING
LCS + Edit Distance + Grid Paths — O(m*n)

15A · Longest Common Subsequence

TIME: O(m*n) SPACE: O(min(m,n)) optimized

1 int longestCommonSubsequence(string t1, string t2) {

2 int m=[Link](), n=[Link]();
3 // Space-optimized: only keep 2 rows
4 vector<int> prev(n+1,0), curr(n+1,0);
5 for (int i=1;i<=m;i++) {
6 for (int j=1;j<=n;j++) {
7 if (t1[i-1]==t2[j-1])
8 curr[j] = prev[j-1]+1; // chars match: extend diagonal
9 else
10 curr[j] = max(prev[j], curr[j-1]); // skip one char
11 }
12 swap(prev, curr);
13 fill([Link](), [Link](), 0);
14 }
15 return prev[n];
16 }

15B · Edit Distance (Levenshtein)

1 int minDistance(string w1, string w2) {

2 int m=[Link](), n=[Link]();
3 vector<vector<int>> dp(m+1, vector<int>(n+1));
4 for (int i=0;i<=m;i++) dp[i][0]=i; // delete all of w1
5 for (int j=0;j<=n;j++) dp[0][j]=j; // insert all of w2
6 for (int i=1;i<=m;i++) {
7 for (int j=1;j<=n;j++) {
8 if (w1[i-1]==w2[j-1])
9 dp[i][j] = dp[i-1][j-1]; // no op
10 else
11 dp[i][j] = 1 + min({dp[i-1][j], // delete
12 dp[i][j-1], // insert
13 dp[i-1][j-1]});// replace
14 }
15 }
16 return dp[m][n];
17 }

DSA Patterns · C++ Notes · Interview Prep Page 31

 2D DP TRICKS

LCS recurrence: match -> dp[i-1][j-1]+1, else max(up, left)

Edit distance: 3 operations — insert(left+1), delete(up+1), replace(diag+1)
Space optimize: only 2 rows needed — swap(prev, curr) after each row
Unique paths: dp[i][j] = dp[i-1][j] + dp[i][j-1] (pure addition)
Longest palindromic subsequence = LCS(s, reverse(s))
Interleaving strings: dp[i][j] = bool — can s1[0..i] + s2[0..j] form s3[0..i+j]

DSA Patterns · C++ Notes · Interview Prep Page 32

 SEC 16 · STATE-MACHINE DP (STOCK PROBLEMS)
held / sold / cooldown states — O(n) O(1)

16A · Buy & Sell Stock with Cooldown

TIME: O(n) SPACE: O(1)

1 // States: held (own stock), sold (just sold), rest (cooldown done)
2 int maxProfit(vector<int>& prices) {
3 int held = INT_MIN, sold = 0, rest = 0;
4 for (int p : prices) {
5 int prev_held = held, prev_sold = sold, prev_rest = rest;
6 held = max(prev_held, prev_rest - p); // keep or buy
7 sold = prev_held + p; // sell today
8 rest = max(prev_rest, prev_sold); // stay resting or end cooldown
9 }
10 return max(sold, rest);
11 }

16B · State Transition Diagram

The three states and their transitions:

1 // State transitions:
2 // REST --buy--> HELD --sell--> SOLD --cooldown--> REST
3 // ^ |
4 // +-------------------(stay rest)----------------------->+
5
6 // General k-transactions variant:
7 // dp[k][0] = max(dp[k][0], dp[k][1] + price) // sell
8 // dp[k][1] = max(dp[k][1], dp[k-1][0] - price) // buy
9
10 // With transaction fee:
11 int maxProfitFee(vector<int>& prices, int fee) {
12 int cash=0, hold=INT_MIN;
13 for (int p : prices) {
14 cash = max(cash, hold + p - fee); // sell
15 hold = max(hold, cash - p); // buy
16 }
17 return cash;
18 }

DSA Patterns · C++ Notes · Interview Prep Page 33

 STATE MACHINE DP TRICKS

Always save previous state values before updating — avoid using updated values
Cooldown: held = max(held, rest - price) (can only buy from rest, not sold)
Fee: deduct fee on sell: cash = max(cash, hold + price - fee)
At most k transactions: 2D array dp[k+1][2] — second dim = hold/not-hold
Unlimited transactions: cash = max(cash, hold+p); hold = max(hold, cash-p)
State machine mental model: draw nodes (states) and edges (transitions) first

DSA Patterns · C++ Notes · Interview Prep Page 34

 SEC 17 · BACKTRACKING
Choose-Explore-Unchoose + Pruning — O(n!) worst case

N-Queens

Word Search Combination Sum

Backtracking

Sudoku Solve Subsets

Permutations

17A · Permutations (all orderings)

TIME: O(n * n!) SPACE: O(n) recursion depth

1 vector<vector<int>> permute(vector<int>& nums) {

2 vector<vector<int>> res;
3 vector<bool> used([Link](), false);
4 vector<int> path;
5 function<void()> bt = [&]() {
6 if ([Link]() == [Link]()) { res.push_back(path); return; }
7 for (int i=0; i<[Link](); i++) {
8 if (used[i]) continue;
9 used[i] = true; // CHOOSE
10 path.push_back(nums[i]);
11 bt(); // EXPLORE
12 path.pop_back(); // UNCHOOSE
13 used[i] = false;
14 }
15 };
16 bt(); return res;
17 }

17B · Combination Sum (reuse elements)

DSA Patterns · C++ Notes · Interview Prep Page 35

 1 vector<vector<int>> combinationSum(vector<int>& cands, int target) {
2 vector<vector<int>> res;
3 vector<int> path;
4 sort([Link](), [Link]()); // sort for pruning
5 function<void(int,int)> bt = [&](int start, int rem) {
6 if (rem==0) { res.push_back(path); return; }
7 for (int i=start; i<[Link](); i++) {
8 if (cands[i] > rem) break; // PRUNE: sorted, no point continuing
9 path.push_back(cands[i]);
10 bt(i, rem - cands[i]); // i (not i+1) allows reuse
11 path.pop_back();
12 }
13 };
14 bt(0, target); return res;
15 }

17C · Word Search in Grid

1 bool exist(vector<vector<char>>& board, string word) {

2 int m=[Link](), n=board[0].size();
3 function<bool(int,int,int)> bt = [&](int r, int c, int k) -> bool {
4 if (k==[Link]()) return true;
5 if (r<0||c<0||r>=m||c>=n||board[r][c]!=word[k]) return false;
6 char tmp = board[r][c];
7 board[r][c] = '#'; // mark visited IN-PLACE
8 bool found = bt(r+1,c,k+1)||bt(r-1,c,k+1)||
9 bt(r,c+1,k+1)||bt(r,c-1,k+1);
10 board[r][c] = tmp; // restore (backtrack)
11 return found;
12 };
13 for (int i=0;i<m;i++) for(int j=0;j<n;j++)
14 if (bt(i,j,0)) return true;
15 return false;
16 }

BACKTRACKING TRICKS

Template: choose(i) -> recurse -> unchoose(i) (always symmetric)

Pruning: sort + break when candidate > remaining (cuts O(n!) to much less)
Subsets: start index prevents duplicates, no 'used' array needed
In-place visited: mark board[r][c]='#', restore after — no extra visited array
Unique permutations: sort + skip if nums[i]==nums[i-1] and !used[i-1]
Combination vs Permutation: comb uses start index, perm uses used[] array

DSA Patterns · C++ Notes · Interview Prep Page 36

 SEC 18 · YEAR-WISE STRATEGY + MASTER COMPLEXITY SHEET
Interview roadmap and quick reference for all patterns

Pattern-First

Company Focus 4th Year Patterns

Interview Prep

Communication 3rd Year Patterns

2nd Year Patterns

Year-wise Focus Patterns

Year Target Programs Key Patterns Execution Focus

2nd Google STEP Arrays, HashMap, Communicate brute-force

Amazon WOW 2-Pointers, Sliding Window then optimize; ask hints
MS Explore

3rd Summer SDE Internship DFS/BFS, DP (1D+2D), Pattern-first approach;

(Return offer pipeline) Backtracking, Intervals O(n)/O(n log n) in 40 min

4th Full-time SDE-1 Multi-BFS, Topo Sort, Edge cases + complexity

Off-campus drives DSU, Mono Stack, LRU justification + design bridge

Master Complexity Cheat Sheet

Pattern Time Space Key Insight

Sliding Window (fixed) O(n) O(1) Add new, remove outgoing

Sliding Window (variable) O(n) O(k) Expand right, shrink left

Two Pointers (convergence) O(n) O(1) Requires sorted input

Two Pointers (in-place) O(n) O(1) Read head + write head

Fast & Slow Pointers O(n) O(1) 2x speed -> cycle meet

In-Place Reversal O(n) O(1) prev-curr-next rewire

Monotonic Stack O(n) O(n) Each element pushed/popped once

DFS (tree/graph) O(V+E) O(h) h = height / recursion depth

BFS (tree/graph) O(V+E) O(w) w = max queue width

Topological Sort O(V+E) O(V) Indegree BFS; cycle if V mismatch

Union-Find O(alpha(n)) O(n) Near-constant per operation

Binary Search O(log n) O(1) Halve search space each step

DSA Patterns · C++ Notes · Interview Prep Page 37

 Binary Search on Answer O(n log R) O(1) R = answer range

Merge Intervals O(n log n) O(n) Sort first, then single pass

1D DP (Kadane's) O(n) O(1) Local max vs global max

2D DP (LCS) O(m*n) O(n) Keep 2 rows for space opt

State Machine DP O(n) O(states) Save prev state before update

Backtracking O(n!) O(n) Prune early to cut branches

Pattern-First Decision: Input -> Algorithm

Input Clue First Pattern to Try

Sorted array / 'find pair' Binary Search or Two Pointers

'Subarray' / 'substring' / 'contiguous' Sliding Window

'Linked list' + 'cycle' Fast & Slow Pointers

'Tree' + 'path/depth/subtree' DFS (recursive)

'Shortest path' / 'levels' / 'nearest' BFS

'Prerequisites' / 'dependencies' / 'ordering' Topological Sort

'Connected components' / 'union' Union-Find

'All permutations/subsets/combinations' Backtracking

'Overlapping subproblems' / 'max/min ways' Dynamic Programming

'Next greater / smaller element' Monotonic Stack

'Merge/insert intervals' / 'meeting rooms' Intervals + Sort

'Minimize the maximum' / 'capacity to ship' Binary Search on Answer

UNIVERSAL INTERVIEW TRICKS

Always discuss brute force first (shows you understand the problem)
State time+space complexity for EVERY solution before writing code
For any new problem: ID input type -> pick pattern -> adapt template
Think out loud: interviewers assess thought process, not just final code
Test with edge cases: empty input, single element, all same, sorted/reverse
mid = lo + (hi-lo)/2 — NEVER lo+hi (overflow) — memorize this forever
BFS for shortest path, DFS for existence/exhaustive — never mix these up

DSA Patterns · C++ Notes · Interview Prep Page 38