🧠 DSA Mastery Roadmap

// 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<int, int> 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);
}

// 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];

// 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);
}

vector<int> 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]++; }

// 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);
}

// 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;

// 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()]);
}

// 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<TreeNode*> 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<int> dist(n, -1);
queue<int> 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); }
}

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

// 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]; }

// 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;
}

vector<vector<int>> result;
vector<int> 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
    }
}

// 1D DP — Climbing Stairs
vector<int> 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<int> 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);
}

struct TrieNode {
    unordered_map<char, TrieNode*> 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;
    }
};

// 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<int> 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