🧠 DSA Mastery Roadmap

Data Structures & Algorithms for Coding Interviews — Complete C++ Reference with LeetCode Problems & Chapter Deep-Dives

13Chapters

150+Problems

C++Templates

13Patterns

📊 Your Progress

0% Loading…

Filter:

Ch0

Big O Notation & Recursion

Beginner No Prerequisites 📄 Chapter Notes

▼

0/4 solved 0%

Key Concepts

Big O: drop constants (O(5n)=O(n)), drop lower-order terms (O(n²+n)=O(n²))
Complexity Hierarchy: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!)
Recursion: every recursive function needs a base case + recursive case
Call stack space = O(depth) — watch for stack overflow on deep recursion
Memoization = cache results to avoid recomputing subproblems

Recursion spaceO(depth) MemoizedO(n) states

```cpp
// Generic recursion template
ReturnType solve(params, state) {
    if (baseCondition) return baseValue;   // 1. Base case
    return solve(smallerParams, newState); // 2. Recursive case
}
// Top-down memoization
unordered_map memo;
int dp(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = dp(n-1) + dp(n-2);
}
```
    

Practice Problems

#	Problem	Difficulty
1	509. Fibonacci Number	Easy
2	70. Climbing Stairs	Easy
3	231. Power of Two	Easy
4	206. Reverse Linked List	Easy

Ch1

Arrays & Strings

Intermediate Prereq: Ch0 📄 Chapter Notes

▼

0/26 solved 0%

1.1 Two Pointers

OPPOSITE ENDS: left=0, right=n-1, move inward — palindrome, two-sum on sorted
SAME DIRECTION: fast/slow pointers — remove duplicates, subsequence check
TWO ARRAYS: one pointer per array — merge sorted arrays, compare sequences

TimeO(n) SpaceO(1)

```cpp
// Opposite ends
int left = 0, right = arr.size() - 1;
while (left < right) {
    if (condition) { left++; right--; }
    else if (tooSmall) left++;
    else right--;
}
// Fast/Slow (same direction)
int slow = 0;
for (int fast = 0; fast < arr.size(); fast++)
    if (condition(arr[fast])) arr[slow++] = arr[fast];
```
    

#	Problem	Difficulty
1	125. Valid Palindrome	Easy
2	167. Two Sum II	Medium
3	344. Reverse String	Easy
4	977. Squares of a Sorted Array	Easy
5	283. Move Zeroes	Easy
6	26. Remove Duplicates from Sorted Array	Easy
7	392. Is Subsequence	Easy
8	15. 3Sum	Medium
9	11. Container With Most Water	Medium
10	42. Trapping Rain Water	Hard

1.2 Sliding Window

DYNAMIC WINDOW: expand right always, shrink left while constraint violated
FIXED WINDOW (size k): slide — add arr[right], remove arr[right-k]
Count of valid subarrays ending at right = right - left + 1

TimeO(n) amortized SpaceO(1) or O(k)

```cpp
// Dynamic window
int left = 0, curr = 0, ans = 0;
for (int right = 0; right < nums.size(); right++) {
    curr += nums[right];
    while (curr > k) curr -= nums[left++];
    ans = max(ans, right - left + 1);
}
// Fixed window (size k)
int curr = 0;
for (int i = 0; i < k; i++) curr += nums[i];
int ans = curr;
for (int i = k; i < nums.size(); i++) {
    curr += nums[i] - nums[i-k];
    ans = max(ans, curr);
}
```
    

#	Problem	Difficulty
11	643. Maximum Average Subarray I	Easy
12	1004. Max Consecutive Ones III	Medium
13	3. Longest Substring Without Repeating Characters	Medium
14	713. Subarray Product Less Than K	Medium
15	209. Minimum Size Subarray Sum	Medium
16	904. Fruit Into Baskets	Medium
17	239. Sliding Window Maximum	Hard
18	76. Minimum Window Substring	Hard

1.3 Prefix Sum

prefix[i] = prefix[i-1] + nums[i-1]. Range sum [l,r] = prefix[r+1] - prefix[l]
Combine with hashmap: store prefix sum frequencies for subarray count problems
2D prefix sums for matrix range queries

TimeO(n) build, O(1) query SpaceO(n)

```cpp vector prefix(nums.size() + 1, 0); for (int i = 0; i < nums.size(); i++) prefix[i+1] = prefix[i] + nums[i]; // Sum nums[l..r] = prefix[r+1] - prefix[l]

// Subarray sum equals k — O(n) unordered_map<int,int> freq; freq[0] = 1; // init: prefix sum 0 seen once int curr = 0, ans = 0; for (int x : nums) { curr += x; ans += freq[curr - k]; freq[curr]++; }

    </div>
    <table class="ch-problem-table">
      <thead><tr><th>✓</th><th>#</th><th>Problem</th><th>Difficulty</th></tr></thead>
      <tbody>
        <tr data-key="ch1-p19" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>19</td><td><a href="https://leetcode.com/problems/running-sum-of-1d-array/" target="_blank" class="problem-link">1480. Running Sum of 1d Array</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch1-p20" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>20</td><td><a href="https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/" target="_blank" class="problem-link">1413. Minimum Value to Get Positive Step by Step Sum</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch1-p21" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>21</td><td><a href="https://leetcode.com/problems/k-radius-subarray-averages/" target="_blank" class="problem-link">2090. K Radius Subarray Averages</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch1-p22" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>22</td><td><a href="https://leetcode.com/problems/range-sum-query-immutable/" target="_blank" class="problem-link">303. Range Sum Query - Immutable</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch1-p23" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>23</td><td><a href="https://leetcode.com/problems/subarray-sum-equals-k/" target="_blank" class="problem-link">560. Subarray Sum Equals K</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch1-p24" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>24</td><td><a href="https://leetcode.com/problems/contiguous-array/" target="_blank" class="problem-link">525. Contiguous Array</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch1-p25" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>25</td><td><a href="https://leetcode.com/problems/product-of-array-except-self/" target="_blank" class="problem-link">238. Product of Array Except Self</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch1-p26" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>26</td><td><a href="https://leetcode.com/problems/find-pivot-index/" target="_blank" class="problem-link">724. Find Pivot Index</a></td><td class="diff-easy">Easy</td></tr>
      </tbody>
    </table>
  </div>
</div>
<!-- ═══════════════════════════════════════════════
     Ch 2 — Hashing
═══════════════════════════════════════════════ -->
<div class="ch-card" id="ch2" data-ch="ch2" style="--ch-accent: linear-gradient(90deg,#00b4d8,#0077b6);">
  <div class="ch-header">
    <div class="ch-num">Ch2</div>
    <div class="ch-title-wrap">
      <div class="ch-title">Hashing — HashMaps & Sets</div>
      <div class="ch-meta">
        <span class="ch-badge">Intermediate</span>
        <span class="ch-badge">Prereq: Ch1</span>
        <a href="/learning/dsa/hashing/ch2-hashing/" class="ch-badge notes-live">📄 Chapter Notes</a>
      </div>
    </div>
    <span class="ch-chevron">▼</span>
  </div>
  <div class="ch-progress-row">
    <div class="ch-prog-bar-wrap"><div class="ch-prog-bar"></div></div>
    <span class="ch-prog-text">0/13 solved</span>
    <span class="ch-prog-pct">0%</span>
  </div>
  <div class="ch-body">
    <div class="ch-section-label">Key Patterns</div>
    <div class="dsa-pattern-box">
      <ul>
        <li><strong>EXISTENCE CHECK:</strong> Use unordered_set for O(1) lookup (duplicates, anagram, pangram)</li>
        <li><strong>FREQUENCY COUNT:</strong> Use unordered_map&lt;T,int&gt; (count chars, elements, words)</li>
        <li><strong>TWO-SUM PATTERN:</strong> Store seen values; for each x, check if (target-x) exists</li>
        <li><strong>GROUPING:</strong> Map key → list of values (group anagrams by sorted string)</li>
        <li><strong>SLIDING WINDOW + HASHMAP:</strong> Track character frequencies in a window</li>
        <li><strong>PREFIX SUM + HASHMAP:</strong> Count subarrays with target sum/property</li>
      </ul>
    </div>
    <div class="ch-complexity">
      <span class="cplx-badge"><span class="cplx-label">Time</span>O(n) average</span>
      <span class="cplx-badge"><span class="cplx-label">Space</span>O(n)</span>
    </div>
    <button class="code-toggle-btn"><span class="caret">▸</span> Show C++ Templates</button>
    <div class="code-block-wrap">
```cpp
// Frequency count
unordered_map<int,int> freq;
for (int x : arr) freq[x]++;
// Two-sum lookup
unordered_map<int,int> seen;
for (int i = 0; i < nums.size(); i++) {
    if (seen.count(target - nums[i])) return {seen[target-nums[i]], i};
    seen[nums[i]] = i;
}
// Group anagrams
unordered_map<string, vector<string>> groups;
for (string& s : strs) {
    string key = s; sort(key.begin(), key.end());
    groups[key].push_back(s);
}

</div>
<table class="ch-problem-table">
  <thead><tr><th>✓</th><th>#</th><th>Problem</th><th>Difficulty</th></tr></thead>
  <tbody>
    <tr data-key="ch2-p1" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>1</td><td><a href="https://leetcode.com/problems/check-if-the-sentence-is-pangram/" target="_blank" class="problem-link">1832. Check if the Sentence Is Pangram</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p2" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>2</td><td><a href="https://leetcode.com/problems/missing-number/" target="_blank" class="problem-link">268. Missing Number</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p3" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>3</td><td><a href="https://leetcode.com/problems/counting-elements/" target="_blank" class="problem-link">1426. Counting Elements</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p4" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>4</td><td><a href="https://leetcode.com/problems/two-sum/" target="_blank" class="problem-link">1. Two Sum</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p5" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>5</td><td><a href="https://leetcode.com/problems/ransom-note/" target="_blank" class="problem-link">383. Ransom Note</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p6" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>6</td><td><a href="https://leetcode.com/problems/jewels-and-stones/" target="_blank" class="problem-link">771. Jewels and Stones</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p7" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>7</td><td><a href="https://leetcode.com/problems/find-players-with-zero-or-one-losses/" target="_blank" class="problem-link">2225. Find Players With Zero or One Losses</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch2-p8" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>8</td><td><a href="https://leetcode.com/problems/largest-unique-number/" target="_blank" class="problem-link">1133. Largest Unique Number</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p9" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>9</td><td><a href="https://leetcode.com/problems/maximum-number-of-balloons/" target="_blank" class="problem-link">1189. Maximum Number of Balloons</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch2-p10" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>10</td><td><a href="https://leetcode.com/problems/group-anagrams/" target="_blank" class="problem-link">49. Group Anagrams</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch2-p11" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>11</td><td><a href="https://leetcode.com/problems/top-k-frequent-elements/" target="_blank" class="problem-link">347. Top K Frequent Elements</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch2-p12" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>12</td><td><a href="https://leetcode.com/problems/subarray-sum-equals-k/" target="_blank" class="problem-link">560. Subarray Sum Equals K</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch2-p13" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>13</td><td><a href="https://leetcode.com/problems/lru-cache/" target="_blank" class="problem-link">146. LRU Cache</a></td><td class="diff-medium">Medium</td></tr>
  </tbody>
</table>

Ch3

Linked Lists

Intermediate Prereq: Ch2 📄 Chapter Notes

▼

0/11 solved 0%

Key Patterns

FAST/SLOW POINTERS (Floyd's): fast moves 2x, slow 1x — middle, cycle, kth from end
REVERSAL: Iterative with prev/curr/next. O(n) time, O(1) space
DUMMY NODE: Add dummy head to simplify edge cases (empty list, removing head)
TWO-POINTER MERGE: Merge two sorted lists by comparing heads

TimeO(n) traversal SpaceO(1) most patterns

```cpp // Fast/slow — find middle ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } // slow = middle

// Reverse iteratively ListNode *prev = nullptr, curr = head; while (curr) { ListNode nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; } // prev = new head

// Merge sorted (dummy head) ListNode dummy(0); ListNode* tail = &dummy; while (l1 && l2) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2;

    </div>
    <table class="ch-problem-table">
      <thead><tr><th>✓</th><th>#</th><th>Problem</th><th>Difficulty</th></tr></thead>
      <tbody>
        <tr data-key="ch3-p1" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>1</td><td><a href="https://leetcode.com/problems/middle-of-the-linked-list/" target="_blank" class="problem-link">876. Middle of the Linked List</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch3-p2" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>2</td><td><a href="https://leetcode.com/problems/remove-duplicates-from-sorted-list/" target="_blank" class="problem-link">83. Remove Duplicates from Sorted List</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch3-p3" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>3</td><td><a href="https://leetcode.com/problems/reverse-linked-list/" target="_blank" class="problem-link">206. Reverse Linked List</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch3-p4" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>4</td><td><a href="https://leetcode.com/problems/reverse-linked-list-ii/" target="_blank" class="problem-link">92. Reverse Linked List II</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch3-p5" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>5</td><td><a href="https://leetcode.com/problems/linked-list-cycle/" target="_blank" class="problem-link">141. Linked List Cycle</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch3-p6" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>6</td><td><a href="https://leetcode.com/problems/merge-two-sorted-lists/" target="_blank" class="problem-link">21. Merge Two Sorted Lists</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch3-p7" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>7</td><td><a href="https://leetcode.com/problems/remove-nth-node-from-end-of-list/" target="_blank" class="problem-link">19. Remove Nth Node From End of List</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch3-p8" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>8</td><td><a href="https://leetcode.com/problems/add-two-numbers/" target="_blank" class="problem-link">2. Add Two Numbers</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch3-p9" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>9</td><td><a href="https://leetcode.com/problems/reorder-list/" target="_blank" class="problem-link">143. Reorder List</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch3-p10" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>10</td><td><a href="https://leetcode.com/problems/lru-cache/" target="_blank" class="problem-link">146. LRU Cache</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch3-p11" data-diff="hard"><td class="solved-cell"><div class="solved-check"></div></td><td>11</td><td><a href="https://leetcode.com/problems/merge-k-sorted-lists/" target="_blank" class="problem-link">23. Merge K Sorted Lists</a></td><td class="diff-hard">Hard</td></tr>
      </tbody>
    </table>
  </div>
</div>
<!-- ═══════════════════════════════════════════════
     Ch 4 — Stacks & Queues
═══════════════════════════════════════════════ -->
<div class="ch-card" id="ch4" data-ch="ch4" style="--ch-accent: linear-gradient(90deg,#06d6a0,#1b9aaa);">
  <div class="ch-header">
    <div class="ch-num">Ch4</div>
    <div class="ch-title-wrap">
      <div class="ch-title">Stacks & Queues</div>
      <div class="ch-meta">
        <span class="ch-badge">Intermediate</span>
        <span class="ch-badge">Prereq: Ch3</span>
        <a href="/learning/dsa/stacks/ch4-stacks-queues/" class="ch-badge notes-live">📄 Chapter Notes</a>
      </div>
    </div>
    <span class="ch-chevron">▼</span>
  </div>
  <div class="ch-progress-row">
    <div class="ch-prog-bar-wrap"><div class="ch-prog-bar"></div></div>
    <span class="ch-prog-text">0/11 solved</span>
    <span class="ch-prog-pct">0%</span>
  </div>
  <div class="ch-body">
    <div class="ch-section-label">4.1 Stacks — Key Patterns</div>
    <div class="dsa-pattern-box">
      <ul>
        <li><strong>MATCHING/VALIDATION:</strong> Push open brackets, pop on close, check match</li>
        <li><strong>MONOTONIC STACK (increasing):</strong> pop smaller than current → next greater element</li>
        <li><strong>MONOTONIC STACK (decreasing):</strong> pop greater than current → next smaller element</li>
        <li><strong>STRING SIMULATION:</strong> Build result char-by-char on a stack</li>
      </ul>
    </div>
    <div class="ch-complexity">
      <span class="cplx-badge"><span class="cplx-label">Time</span>O(n)</span>
      <span class="cplx-badge"><span class="cplx-label">Space</span>O(n)</span>
    </div>
    <button class="code-toggle-btn"><span class="caret">▸</span> Show C++ Templates</button>
    <div class="code-block-wrap">
```cpp
// Monotonic stack — Next Greater Element
vector<int> ans(nums.size(), -1);
stack<int> stk;
for (int i = 0; i < nums.size(); i++) {
    while (!stk.empty() && nums[i] > nums[stk.top()])
        { ans[stk.top()] = nums[i]; stk.pop(); }
    stk.push(i);
}
// Bracket matching
stack<char> stk;
for (char c : s) {
    if (c == '(') stk.push(c);
    else if (!stk.empty() && stk.top() == '(') stk.pop();
    else return false;
}
return stk.empty();
// Deque — sliding window max
deque<int> dq;
for (int i = 0; i < nums.size(); i++) {
    while (!dq.empty() && dq.front() < i-k+1) dq.pop_front();
    while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
    dq.push_back(i);
    if (i >= k-1) ans.push_back(nums[dq.front()]);
}

</div>
<table class="ch-problem-table">
  <thead><tr><th>✓</th><th>#</th><th>Problem</th><th>Difficulty</th></tr></thead>
  <tbody>
    <tr data-key="ch4-p1" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>1</td><td><a href="https://leetcode.com/problems/valid-parentheses/" target="_blank" class="problem-link">20. Valid Parentheses</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch4-p2" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>2</td><td><a href="https://leetcode.com/problems/simplify-path/" target="_blank" class="problem-link">71. Simplify Path</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch4-p3" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>3</td><td><a href="https://leetcode.com/problems/make-the-string-great/" target="_blank" class="problem-link">1544. Make The String Great</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch4-p4" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>4</td><td><a href="https://leetcode.com/problems/next-greater-element-i/" target="_blank" class="problem-link">496. Next Greater Element I</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch4-p5" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>5</td><td><a href="https://leetcode.com/problems/online-stock-span/" target="_blank" class="problem-link">901. Online Stock Span</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch4-p6" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>6</td><td><a href="https://leetcode.com/problems/daily-temperatures/" target="_blank" class="problem-link">739. Daily Temperatures</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch4-p7" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>7</td><td><a href="https://leetcode.com/problems/asteroid-collision/" target="_blank" class="problem-link">735. Asteroid Collision</a></td><td class="diff-medium">Medium</td></tr>
    <tr data-key="ch4-p8" data-diff="hard"><td class="solved-cell"><div class="solved-check"></div></td><td>8</td><td><a href="https://leetcode.com/problems/largest-rectangle-in-histogram/" target="_blank" class="problem-link">84. Largest Rectangle in Histogram</a></td><td class="diff-hard">Hard</td></tr>
    <tr data-key="ch4-p9" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>9</td><td><a href="https://leetcode.com/problems/moving-average-from-data-stream/" target="_blank" class="problem-link">346. Moving Average from Data Stream</a></td><td class="diff-easy">Easy</td></tr>
    <tr data-key="ch4-p10" data-diff="hard"><td class="solved-cell"><div class="solved-check"></div></td><td>10</td><td><a href="https://leetcode.com/problems/sliding-window-maximum/" target="_blank" class="problem-link">239. Sliding Window Maximum</a></td><td class="diff-hard">Hard</td></tr>
    <tr data-key="ch4-p11" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>11</td><td><a href="https://leetcode.com/problems/design-circular-queue/" target="_blank" class="problem-link">622. Design Circular Queue</a></td><td class="diff-medium">Medium</td></tr>
  </tbody>
</table>

Ch5

Trees & Graphs

Advanced Prereq: Ch4 📄 Chapter Notes

▼

0/22 solved 0%

5.1 Binary Tree — DFS

PREORDER (root→left→right): copying, serializing trees
INORDER (left→root→right): sorted order for BST
POSTORDER (left→right→root): deletion, computing subtree properties
GLOBAL vs LOCAL: use a global variable for answers spanning multiple nodes

TimeO(n) SpaceO(h) stack

```cpp
// Recursive DFS
int dfs(TreeNode* node) {
    if (!node) return 0;
    int left = dfs(node->left), right = dfs(node->right);
    return 1 + max(left, right); // example: height
}
// BFS level-order
queue q; q.push(root);
while (!q.empty()) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
        TreeNode* node = q.front(); q.pop();
        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
}
// Graph BFS — shortest path
vector dist(n, -1);
queue q; q.push(start); dist[start] = 0;
while (!q.empty()) {
    int node = q.front(); q.pop();
    for (int nei : adj[node])
        if (dist[nei]==-1) { dist[nei]=dist[node]+1; q.push(nei); }
}
```
    

#	Problem	Difficulty
1	111. Minimum Depth of Binary Tree	Easy
2	104. Maximum Depth of Binary Tree	Easy
3	543. Diameter of Binary Tree	Easy
4	1026. Maximum Difference Between Node and Ancestor	Medium
5	113. Path Sum II	Medium
6	236. Lowest Common Ancestor of a Binary Tree	Medium
7	124. Binary Tree Maximum Path Sum	Hard
8	102. Binary Tree Level Order Traversal	Medium
9	1302. Deepest Leaves Sum	Medium
10	103. Binary Tree Zigzag Level Order Traversal	Medium
11	637. Average of Levels in Binary Tree	Easy
12	701. Insert into a Binary Search Tree	Medium
13	270. Closest Binary Search Tree Value	Easy
14	98. Validate Binary Search Tree	Medium
15	230. Kth Smallest Element in a BST	Medium
16	1971. Find if Path Exists in Graph	Easy
17	695. Max Area of Island	Medium
18	1926. Nearest Exit from Entrance in Maze	Medium
19	200. Number of Islands	Medium
20	207. Course Schedule	Medium
21	133. Clone Graph	Medium
22	127. Word Ladder	Hard

Ch6

Heaps & Priority Queues

Intermediate Prereq: Ch5 📄 Chapter Notes

▼

0/8 solved 0%

Key Patterns

TOP K: Min-heap of size k — push each element; if size > k, pop. Heap = top k largest
K-WAY MERGE: Push (value, listIndex, elemIndex) into heap; always pop smallest
RUNNING MEDIAN: Max-heap for lower half + min-heap for upper half
Trigger: 'Smallest/Largest K elements' → heap. C++ default is max-heap; use greater<int> for min

Push/PopO(log n) PeekO(1)

```cpp
// Min-heap
priority_queue, greater> minH;
// Top-K largest using min-heap of size K
priority_queue, greater> pq;
for (int x : nums) { pq.push(x); if (pq.size() > k) pq.pop(); }
// pq.top() = kth largest
// Custom comparator
auto cmp = [](pair& a, pair& b){ return a.first > b.first; };
priority_queue, vector>, decltype(cmp)> pq(cmp);
```
    

#	Problem	Difficulty
1	1962. Remove Stones to Minimize the Total	Medium
2	1167. Minimum Cost to Connect Sticks	Medium
3	215. Kth Largest Element in an Array	Medium
4	973. K Closest Points to Origin	Medium
5	703. Kth Largest Element in a Stream	Easy
6	295. Find Median from Data Stream	Hard
7	621. Task Scheduler	Medium
8	23. Merge K Sorted Lists	Hard

Ch7

Greedy Algorithms

Intermediate Prereq: Ch3 📄 Chapter Notes

▼

0/8 solved 0%

Key Patterns

SORT FIRST: Most greedy problems require sorting by some key (weight, ratio, end time)
INTERVAL SCHEDULING: Sort by end time — greedily take non-overlapping intervals
EXCHANGE ARGUMENT: Prove swapping adjacent elements doesn't improve solution
Ask: 'Does taking the best local choice block a better global solution?' If no → greedy works

TimeO(n log n) with sort SpaceO(1)

```cpp
// Interval scheduling — max non-overlapping intervals
sort(intervals.begin(), intervals.end(),
    [](auto& a, auto& b){ return a[1] < b[1]; }); // sort by end
int count = 0, prevEnd = INT_MIN;
for (auto& iv : intervals)
    if (iv[0] >= prevEnd) { count++; prevEnd = iv[1]; }
```
    

#	Problem	Difficulty
1	1323. Maximum 69 Number	Easy
2	1710. Maximum Units on a Truck	Easy
3	1338. Reduce Array Size to The Half	Medium
4	435. Non-overlapping Intervals	Medium
5	55. Jump Game	Medium
6	45. Jump Game II	Medium
7	134. Gas Station	Medium
8	135. Candy	Hard

Ch8

Binary Search

Intermediate Prereq: Ch1 📄 Chapter Notes

▼

0/9 solved 0%

Key Patterns

ON SORTED ARRAY: Classic search / find leftmost or rightmost position
ON ANSWER SPACE: Binary search on the answer when feasibility is monotonic
FIND LEFTMOST: Use 'left = mid + 1' when condition met — pushes left boundary right
Trigger: 'minimize the maximum' or 'maximize the minimum' → binary search on answer

TimeO(log n) SpaceO(1)

```cpp
// Standard binary search
int lo = 0, hi = nums.size()-1;
while (lo <= hi) {
    int mid = lo + (hi-lo)/2;  // avoid overflow
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) lo = mid+1;
    else hi = mid-1;
}
// Binary search on answer (minimise)
int lo = minVal, hi = maxVal, ans = hi;
while (lo <= hi) {
    int mid = lo + (hi-lo)/2;
    if (feasible(mid)) { ans = mid; hi = mid-1; }
    else lo = mid+1;
}
```
    

#	Problem	Difficulty
1	704. Binary Search	Easy
2	35. Search Insert Position	Easy
3	2389. Longest Subsequence With Limited Sum	Easy
4	1283. Find the Smallest Divisor Given a Threshold	Medium
5	410. Split Array Largest Sum	Hard
6	875. Koko Eating Bananas	Medium
7	162. Find Peak Element	Medium
8	33. Search in Rotated Sorted Array	Medium
9	4. Median of Two Sorted Arrays	Hard

Ch9

Backtracking

Advanced Prereq: Ch0 Recursion 📄 Chapter Notes

▼

0/11 solved 0%

Key Patterns

GENERATION: Build all permutations/subsets/combinations — just enumerate
CONSTRAINED: Prune early when constraint violated (sum exceeds target)
Template: choose → recurse → unchoose (restore state)
Use 'start' index to avoid re-using earlier elements in combination problems
Use 'used[]' boolean array for permutations to avoid duplicate positions
Time: O(n! × n) permutations, O(2ⁿ × n) subsets — always exponential

SubsetsO(2ⁿ × n) PermsO(n! × n)

```cpp
vector> result;
vector current;
void backtrack(int start) {
    if (isComplete()) { result.push_back(current); return; }
    for (int i = start; i < candidates.size(); i++) {
        if (shouldPrune(i)) continue;
        current.push_back(candidates[i]);  // choose
        backtrack(i + 1);                  // recurse
        current.pop_back();                // unchoose
    }
}
```
    

#	Problem	Difficulty
1	797. All Paths From Source to Target	Medium
2	17. Letter Combinations of a Phone Number	Medium
3	22. Generate Parentheses	Medium
4	967. Numbers With Same Consecutive Differences	Medium
5	216. Combination Sum III	Medium
6	78. Subsets	Medium
7	46. Permutations	Medium
8	39. Combination Sum	Medium
9	79. Word Search	Medium
10	51. N-Queens	Hard
11	37. Sudoku Solver	Hard

Ch10

Dynamic Programming

Advanced Prereq: Ch0, Ch9 📄 Chapter Notes

▼

0/11 solved 0%

Key Patterns

Step 1: Define what dp[i] (or dp[i][j]) represents
Step 2: Find the recurrence relation (transition)
Step 3: Identify base cases
Step 4: Determine iteration order (ensure subproblems solved before needed)
DP vs Greedy: DP explores all choices; Greedy makes one. Use DP when Greedy fails

1D DPO(n) 2D DPO(m×n)

```cpp
// 1D DP — Climbing Stairs
vector dp(n+1, 0); dp[0]=1; dp[1]=1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
// Coin Change (unbounded knapsack)
vector dp(amount+1, INT_MAX); dp[0]=0;
for (int i = 1; i <= amount; i++)
    for (int coin : coins)
        if (coin<=i && dp[i-coin]!=INT_MAX) dp[i]=min(dp[i],dp[i-coin]+1);
// State machine DP (Stock with cooldown)
int hold = -prices[0], sold = 0, rest = 0;
for (int i = 1; i < prices.size(); i++) {
    int ph=hold,ps=sold,pr=rest;
    hold=max(ph,pr-prices[i]); sold=ph+prices[i]; rest=max(pr,ps);
}
```
    

#	Problem	Difficulty
1	70. Climbing Stairs	Easy
2	746. Min Cost Climbing Stairs	Easy
3	322. Coin Change	Medium
4	714. Best Time to Buy and Sell Stock with Transaction Fee	Medium
5	309. Best Time to Buy and Sell Stock with Cooldown	Medium
6	63. Unique Paths II	Medium
7	931. Minimum Falling Path Sum	Medium
8	198. House Robber	Medium
9	1143. Longest Common Subsequence	Medium
10	72. Edit Distance	Medium
11	139. Word Break	Medium

Ch11

Bonus Topics — Tries, Bit Manipulation, Intervals

Advanced 📄 Tries & Intervals Notes ⚙️ Bit Manipulation Deep-Dive

▼

0/6 solved 0%

11.1 Tries (Prefix Trees)

Store strings character by character. Each node = one character; isEnd flag marks valid word
O(m) insert and search where m = string length. Use for: autocomplete, prefix search

```cpp
struct TrieNode {
    unordered_map children;
    bool isEnd = false;
};
class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (!curr->children.count(c)) curr->children[c] = new TrieNode();
            curr = curr->children[c];
        }
        curr->isEnd = true;
    }
    bool search(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (!curr->children.count(c)) return false;
            curr = curr->children[c];
        }
        return curr->isEnd;
    }
};
```
    

11.2 Bit Manipulation

POWER OF TWO: n > 0 && (n & (n-1)) == 0 — exactly one bit set
CLEAR LOWEST SET BIT: n & (n-1) — use in Kernighan popcount loop O(set bits)
ISOLATE LOWEST SET BIT: n & (-n) — rightmost 1 preserved, rest zero
XOR TRICK: a^a=0, a^0=a — cancel pairs; find unique element in O(n)/O(1)
SET / CLEAR / TOGGLE / CHECK: x|=(1<<n) / x&=~(1<<n) / x^=(1<<n) / (x>>n)&1
EXTRACT BITFIELD: (x >> start) & ((1 << width) - 1) — packet headers, hardware registers
BITMASK DP: state = subset bitmask of N elements; viable when N ≤ 20

Bit opsO(1) Popcount loopO(set bits) Bitmask DPO(2ⁿ · n)

```cpp // Core mask operations x |= (1 << n); // SET bit n x &= ~(1 << n); // CLEAR bit n x ^= (1 << n); // TOGGLE bit n int b = (x >> n) & 1; // CHECK bit n (returns 0 or 1)

// Power of two? bool isPow2 = x > 0 && (x & (x-1)) == 0;

// Count set bits — Brian Kernighan O(set bits) int cnt = 0; while (x) { x &= x-1; cnt++; } // clears lowest set bit each iteration

// XOR — find single non-duplicate in O(n) / O(1) (LC 136) int res = 0; for (int n : nums) res ^= n; // paired elements cancel: x^x=0

// Count bits for 0..n — DP O(n) (LC 338) vector dp(n+1); for (int i = 1; i <= n; i++) dp[i] = dp[i >> 1] + (i & 1);

// Extract bitfield [start, start+width) uint32_t field = (x >> start) & ((1 << width) - 1); // Insert pattern: x = (x & ~mask) | (pattern << start) // where mask = ((1 << width) - 1) << start

    </div>
    <div style="margin:.8rem 0;display:flex;flex-wrap:wrap;gap:.5rem;">
      <a href="/learning/dsa/bit-manipulation/" style="display:inline-flex;align-items:center;gap:.3rem;padding:.4rem .9rem;background:#f5f3ff;border:1.5px solid #7c3aed;border-radius:7px;font-size:.82rem;font-weight:700;color:#6d28d9;text-decoration:none;">⚙️ Full Deep-Dive (10 tabs)</a>
      <a href="/learning/dsa/bit-manipulation/systems-problems/" style="display:inline-flex;align-items:center;gap:.3rem;padding:.4rem .9rem;background:#fff7ed;border:1.5px solid #ea580c;border-radius:7px;font-size:.82rem;font-weight:700;color:#c2410c;text-decoration:none;">🔧 Systems Problems</a>
      <a href="/learning/dsa/bit-manipulation/debugging/" style="display:inline-flex;align-items:center;gap:.3rem;padding:.4rem .9rem;background:#e3f2fd;border:1.5px solid #42a5f5;border-radius:7px;font-size:.82rem;font-weight:700;color:#1565c0;text-decoration:none;">🐛 Debugging Guide</a>
      <a href="/learning/dsa/bit-manipulation/bit-manipulation-problems/" style="display:inline-flex;align-items:center;gap:.3rem;padding:.4rem .9rem;background:#1a1060;border-radius:7px;font-size:.82rem;font-weight:700;color:#fff;text-decoration:none;">🎯 Practice Problems →</a>
    </div>
    <div class="ch-section-label">Practice Problems</div>
    <table class="ch-problem-table">
      <thead><tr><th>✓</th><th>#</th><th>Problem</th><th>Difficulty</th></tr></thead>
      <tbody>
        <tr data-key="ch11-p1" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>1</td><td><a href="https://leetcode.com/problems/implement-trie-prefix-tree/" target="_blank" class="problem-link">208. Implement Trie (Prefix Tree)</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch11-p2" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>2</td><td><a href="https://leetcode.com/problems/search-suggestions-system/" target="_blank" class="problem-link">1268. Search Suggestions System</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch11-p3" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>3</td><td><a href="https://leetcode.com/problems/single-number/" target="_blank" class="problem-link">136. Single Number (XOR)</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch11-p4" data-diff="easy"><td class="solved-cell"><div class="solved-check"></div></td><td>4</td><td><a href="https://leetcode.com/problems/number-of-1-bits/" target="_blank" class="problem-link">191. Number of 1 Bits</a></td><td class="diff-easy">Easy</td></tr>
        <tr data-key="ch11-p5" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>5</td><td><a href="https://leetcode.com/problems/insert-interval/" target="_blank" class="problem-link">57. Insert Interval</a></td><td class="diff-medium">Medium</td></tr>
        <tr data-key="ch11-p6" data-diff="medium"><td class="solved-cell"><div class="solved-check"></div></td><td>6</td><td><a href="https://leetcode.com/problems/merge-intervals/" target="_blank" class="problem-link">56. Merge Intervals</a></td><td class="diff-medium">Medium</td></tr>
      </tbody>
    </table>
  </div>
</div>
<!-- ═══════════════════════════════════════════════
     Ch 12 — Study Plan & Cheatsheet
═══════════════════════════════════════════════ -->
<div class="ch-card" id="ch12" data-ch="ch12" style="--ch-accent: linear-gradient(90deg,#00c9a7,#00b4d8);">
  <div class="ch-header">
    <div class="ch-num">Ch12</div>
    <div class="ch-title-wrap">
      <div class="ch-title">Study Plan & Complexity Cheatsheet</div>
      <div class="ch-meta">
        <span class="ch-badge">Reference</span>
        <a href="/learning/dsa/ch12-cheat-sheet/" class="ch-badge notes-live">📄 Chapter Notes</a>
      </div>
    </div>
    <span class="ch-chevron">▼</span>
  </div>
  <div class="ch-progress-row" style="display:none;"></div>
  <div class="ch-body">
    <div class="ch-section-label">Phase 1 — Foundations (Weeks 1–4)</div>
    <div class="dsa-pattern-box">
      <ul>
        <li>Week 1: Ch0 Big O + Ch1 Two Pointers. Solve all Easy problems.</li>
        <li>Week 2: Ch1 Sliding Window + Prefix Sum. Solve all Easy + 2 Medium.</li>
        <li>Week 3: Ch2 Hashing. Core patterns — Two Sum, freq count, grouping.</li>
        <li>Week 4: Ch3 Linked Lists. All patterns — fast/slow, reversal, merge.</li>
      </ul>
    </div>
    <div class="ch-section-label">Phase 2 — Core (Weeks 5–9)</div>
    <div class="dsa-pattern-box">
      <ul>
        <li>Week 5: Ch4 Stacks (monotonic, bracket matching).</li>
        <li>Week 6–7: Ch5 Trees — DFS first (preorder, postorder, LCA), then BFS + BST.</li>
        <li>Week 8: Ch5 Graphs — DFS + BFS + Union-Find.</li>
        <li>Week 9: Ch6 Heaps + Ch7 Greedy.</li>
      </ul>
    </div>
    <div class="ch-section-label">Phase 3 — Advanced (Weeks 10–13)</div>
    <div class="dsa-pattern-box">
      <ul>
        <li>Week 10: Ch8 Binary Search — standard + answer space search.</li>
        <li>Week 11: Ch9 Backtracking — all generation/constrained problems.</li>
        <li>Week 12–13: Ch10 DP — 1D, 2D, state machine, knapsack.</li>
      </ul>
    </div>
    <div class="ch-section-label">Complexity Cheatsheet</div>
    <div class="cheatsheet-grid">
      <div class="cheatsheet-card">
        <h4>Array / String</h4>
        <table><tr><td>Access</td><td>O(1)</td></tr><tr><td>Search</td><td>O(n)</td></tr><tr><td>Insert/Delete</td><td>O(n)</td></tr><tr><td>Append</td><td>O(1) amort.</td></tr></table>
      </div>
      <div class="cheatsheet-card">
        <h4>HashMap / HashSet</h4>
        <table><tr><td>Insert</td><td>O(1) avg</td></tr><tr><td>Lookup</td><td>O(1) avg</td></tr><tr><td>Delete</td><td>O(1) avg</td></tr><tr><td>Worst case</td><td>O(n)</td></tr></table>
      </div>
      <div class="cheatsheet-card">
        <h4>Binary Tree</h4>
        <table><tr><td>DFS / BFS</td><td>O(n)</td></tr><tr><td>BST search</td><td>O(h)</td></tr><tr><td>BST balanced</td><td>O(log n)</td></tr><tr><td>Space</td><td>O(h) stack</td></tr></table>
      </div>
      <div class="cheatsheet-card">
        <h4>Heap</h4>
        <table><tr><td>Push</td><td>O(log n)</td></tr><tr><td>Pop</td><td>O(log n)</td></tr><tr><td>Peek</td><td>O(1)</td></tr><tr><td>Build</td><td>O(n)</td></tr></table>
      </div>
      <div class="cheatsheet-card">
        <h4>Sorting</h4>
        <table><tr><td>std::sort</td><td>O(n log n)</td></tr><tr><td>Counting sort</td><td>O(n+k)</td></tr><tr><td>Radix sort</td><td>O(nk)</td></tr><tr><td>Merge sort</td><td>O(n log n)</td></tr></table>
      </div>
      <div class="cheatsheet-card">
        <h4>Graph</h4>
        <table><tr><td>BFS / DFS</td><td>O(V+E)</td></tr><tr><td>Dijkstra</td><td>O((V+E)log V)</td></tr><tr><td>Union-Find</td><td>O(α(n))≈O(1)</td></tr><tr><td>Topo sort</td><td>O(V+E)</td></tr></table>
      </div>
    </div>
  </div>
</div>
</div><!-- end .dsa-chapters -->
<div style="text-align:center;padding:2rem 0 1rem;">
  <a href="/roadmap/" style="display:inline-block;padding:0.6rem 1.4rem;background:linear-gradient(135deg,#00c9a7,#00b4d8);color:#fff;border-radius:8px;text-decoration:none;font-size:0.9rem;font-weight:700;">← Back to All Roadmaps</a>
</div>


<script src="/assets/js/dsa-roadmap.js" defer></script>