Module 00: The Master Problem-Solving Engine & Pattern Recognition Framework

Goal: Train your brain to look at ANY unseen Data Structures & Algorithms problem and systematically identify the optimal pattern, data structure, and time/space complexity within 60 seconds.
Target Audience: Anyone preparing for Top-Tier Tech / FAANG interviews who wants to move from memorizing individual LeetCode solutions to developing universal problem-solving intuition.

📑 Table of Contents

The Mindset Shift: Why Memorization Fails
The Grand Problem-to-Pattern Decision Tree (ASCII Engine)
The "Constraint $\to$ Target Big-O $\to$ Algorithm" Cheat Matrix
The 25+ Keyword & Linguistic Signal "Rosetta Stone"
The 5 Universal Problem-Solving Techniques
The 6-Step Problem Dissection Protocol
3 End-to-End Case Studies: Tracing Mental Reasoning
The Deliberate Practice Protocol: How to Never Forget Patterns

1. The Mindset Shift: Why Memorization Fails

Most people practice DSA the wrong way:

❌ BAD APPROACH:
Read Problem ──► Try for 5 mins ──► Get Stuck ──► Look at Solution ──► Memorize Code
(Result: Blank out on any new problem with a slight variation)

✅ THE PATTERN RECOGNITION APPROACH:
Read Problem ──► Extract Constraints & Signals ──► Traverse Decision Tree ──► Match Pattern ──► Apply Template
(Result: You can solve 2,000+ problems by mastering just 20 core patterns)

Every DSA problem is simply a combination of:

An Input Domain (Array, String, Matrix, Tree, Graph, Stream, Numbers)
A Goal / Objective (Search, Optimize Min/Max, Count, Check Validity, Generate Combinations)
A Constraint Boundary (Time limit, Space limit, Monotonicity, Subarray vs Subsequence)

Your job is not to invent a new algorithm during the interview. Your job is to diagnose which of the known 20 patterns matches this problem's DNA.

2. The Grand Problem-to-Pattern Decision Tree (ASCII Engine)

Use this diagnostic flowchart whenever you read an unfamiliar problem:

                                  WHAT IS THE PRIMARY INPUT & GOAL?
                                                  │
         ┌────────────────────────┬───────────────┴───────────────┬────────────────────────┐
         ▼                        ▼                               ▼                        ▼
  [ ARRAYS / STRINGS ]       [ NON-LINEAR ]               [ OPTIMIZATION ]          [ COMBINATORICS ]
         │                        │                               │                        │
         ├─ Is it Sorted?         ├─ Parent/Child hierarchy?      ├─ Min/Max of something? ├─ Generate all subsets/
         │  ├─ YES: Two Pointers  │  └─► Tree DFS / BFS           │  ├─ Continuous search     permutations?
         │  │       Binary Search │                               │  │  space? (Monotonic) └─► Backtracking
         │  └─ NO: Hash Map /     ├─ Network / Dependencies?      │  │  └─► Binary Search      (DFS with pruning)
         │         Prefix Sum     │  ├─ Unweighted shortest path? │  │      on Answer Range
         │                        │  │  └─► BFS (Queue)           │  │                     ├─ Count total ways?
         ├─ Contiguous Subarray?  │  ├─ Directed dependencies?    │  ├─ Overlapping        └─► Dynamic Programming
         │  ├─ Size K or Window?  │  │  └─► Kahn's TopoSort       │  │  subproblems?           (1D / 2D DP)
         │  │  └─► Sliding Window │  ├─ Weighted shortest path?   │  │  └─► DP (Knapsack,
         │  ├─ Subarray Sum == K? │  │  └─► Dijkstra (Min-Heap)   │  │      Interval, LCS) ├─ Small N (N <= 20)?
         │  │  └─► Prefix Sum +   │  └─ Connected components?     │  │                     └─► Bitmask DP
         │  │      Hash Map       │     └─► DSU / DFS FloodFill   │  └─ Greedy choice
         │  └─ Max Sum Subarray?  │                               │     always optimal?
         │     └─► Kadane's       ├─ Top K / Stream / Dynamic?    │     └─► Greedy Sort /
         │                        │  └─► Binary Heap / Priority Q │         Interval Sweep
         ├─ Finding Next Greater? │                               │
         │  └─► Monotonic Stack   ├─ Prefix / Autocomplete?       └─ Range queries + updates?
         │                        │  └─► Trie                     └─► Segment Tree / Fenwick
         └─ Numbers in [1, N]?    │
            └─► Cyclic Sort       └─ Overlapping Intervals?
                                     └─► Sort by Start/End + Sweep Line

3. The "Constraint $\to$ Target Big-O $\to$ Algorithm" Cheat Matrix

In competitive programming and technical interviews, the maximum input size $N$ gives away the intended time complexity before you write a single line of code!

Standard CPU operations per second in C++: $\approx 10^8$ operations in 1.0 second.

Input Size ($N$)	Target Time Complexity	Candidate Algorithmic Patterns
$N \le 10$	$O(N!) \text{ or } O(N^2 \cdot 2^N)$	Permutations, Travelling Salesperson, Brute force Backtracking
$N \le 20$	$O(2^N) \text{ or } O(N \cdot 2^N)$	Subsets, Bitmask Dynamic Programming, Meet-in-the-Middle
$N \le 100$	$O(N^4) \text{ or } O(N^3)$	Floyd-Warshall (All-Pairs Shortest Path), 3D/4D DP, Matrix Chain
$N \le 1,000$	$O(N^2)$	2D Dynamic Programming, 2-Pointer nested loops, Bubble/Insertion, All Pairs
$N \le 10^5$	$O(N \log N) \text{ or } O(N)$	Sorting, Binary Search, Heaps, Merge Sort, Segment Trees, Monotonic Stack, Sliding Window, Two Pointers, Hash Table
$N \le 10^6$	$O(N)$	Linear Traversal, Prefix Sums, Kadane's Algorithm, BFS/DFS, DSU, Hash Map
$N \ge 10^9$	$O(\log N) \text{ or } O(1)$	Binary Search, Bit Manipulation, Fast Matrix Exponentiation, Math / Modulo formulas

Interview Pro-Tip: When the interviewer specifies $N = 10^5$, immediately rule out all $O(N^2)$ solutions. You must find an $O(N \log N)$ or $O(N)$ approach!

4. The 25+ Keyword & Linguistic Signal "Rosetta Stone"

Interview problems use specific language that directly signals the underlying pattern:

If the problem description says...	It almost always means...	Primary Data Structure / Pattern
"Find the shortest path / minimum steps in an unweighted grid/graph"	Breadth-First Search	`std::queue` (BFS)
"Find the shortest path in a weighted graph with positive weights"	Dijkstra's Algorithm	`std::priority_queue` (Min-Heap)
"Find K largest / K smallest / Top K frequent elements"	Priority Queue / QuickSelect	Min-Heap of size K (`std::priority_queue`)
"Continuous data stream where we need running median"	Two Balancing Heaps	Max-Heap (lower half) + Min-Heap (upper half)
"Contiguous subarray with sum equals K (contains negative numbers)"	Prefix Sum + Hash Map	`std::unordered_map<int, int>` storing running sum
"Contiguous subarray / substring satisfying condition (positive numbers only)"	Sliding Window	Two Pointers (Expanding Right, Shrinking Left)
"Find next greater / smaller element, daily warmer temperature, histogram area"	Monotonic Stack	`std::stack` storing indices in increasing/decreasing order
"Array contains elements from 1 to N, find missing or duplicate numbers"	Cyclic Sort	In-place swapping ($A[i] \leftrightarrow A[A[i]-1]$)
"Minimize the maximum... / Maximize the minimum..."	Binary Search on Answer Space	`low = min_possible, high = max_possible`, feasibility function
"Overlapping time intervals / meeting rooms / schedule tasks"	Interval Sorting & Sweep	Sort intervals by `start` or `end` time
"Given course prerequisites / build dependencies / compile order"	Topological Sorting	Kahn's In-Degree BFS or DFS 3-coloring
"Find if two elements belong to same group / accounts merge / connected components"	Disjoint Set Union (DSU)	Union-Find with Rank & Path Compression
"Prefix matching / word dictionary / autocomplete"	Trie (Prefix Tree)	Custom Trie Node (`children[26]`, `isEnd`)
"Maximum XOR of two numbers in an array"	Bitwise Trie	Trie with binary bits (0 and 1)
"Find all possible combinations / permutations / partitions"	Backtracking	Recursive DFS with Choose $\to$ Explore $\to$ Unchoose
"Count number of ways to reach / minimum cost with overlapping choices"	Dynamic Programming	1D / 2D DP Table (Memoization or Tabulation)
"Partition array into subsets with equal sum"	0/1 Knapsack DP	1D array traversed in REVERSE
"Can use items unlimited number of times to make a target sum"	Unbounded Knapsack DP	1D array traversed FORWARD
"Subsequence problem on two strings (matching, edit distance)"	2D String Dynamic Programming	$dp[i][j]$ representing prefixes of $S_1$ and $S_2$
"Circular array / list"	Modulo Arithmetic / Fast-Slow	Loop size $2N$ with `index % N`
"Find lowest common ancestor in tree / max path between any two nodes"	Bottom-Up Tree DFS	Post-Order Traversal passing information from children to parent
"Range sum queries with frequent point updates"	Segment Tree / Fenwick Tree	Array of size $4N$ or BIT array
"Bit operations on elements appearing twice except one / power of two"	XOR & Bit Manipulation	`n & (n - 1)`, `a ^ b ^ a = b`
"Matrix / Grid containing 1s and 0s (islands, water flow)"	Matrix DFS / BFS / Multi-source	4-directional traversal with in-place sink marking

5. The 5 Universal Problem-Solving Techniques

When you encounter a problem that does not immediately scream a pattern, apply these 5 universal thinking tools:

Technique 1: Bottleneck Analysis & Wasted Work Elimination

Write down the naive $O(N^2)$ or $O(2^N)$ brute force solution.
Ask: "What specific operation is being done repeatedly and taking the most time?"
- Repeated linear lookup? $\implies$ Replace with Hash Map ($O(1)$) or BST ($O(\log N)$).
- Repeated range sum calculation? $\implies$ Replace with Prefix Sum ($O(1)$).
- Repeated min/max extraction? $\implies$ Replace with Heap ($O(\log N)$) or Monotonic Stack ($O(1)$ amortized).

Technique 2: Binary Search on Answer Space (Monotonic Feasibility)

Whenever a problem asks to "Find the minimum $X$ such that condition $P(X)$ holds", check if $P(X)$ is monotonic:
- If $P(X)$ is true for $X = 10$, is it guaranteed true for all $X \ge 10$?
- If YES $\implies$ Do NOT binary search the input array. Binary search the RANGE OF POSSIBLE ANSWERS (low = 1, high = max_bound) and write a simple greedy $O(N)$ feasibility checker bool canDo(int X). Total time: $O(N \log(\text{Range}))$.

Search Space:  [ 1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ]
Feasible?       F    F    F    F    T    T    T    T    T
                                    ▲
                         Binary search finds the boundary (5)!

Technique 3: Preprocessing & Invariant Creation

If the array is unsorted and problem asks for pairs/triplets $\implies$ Sort the array first ($O(N \log N)$)! Sorting introduces monotonicity, enabling Two Pointers and Binary Search.
Precalculate Prefix Sums, Suffix Minimums, or Frequency Arrays before running the main algorithm.

Technique 4: Invariant Maintenance (Monotonic Structures)

Maintain a data structure where elements are strictly increasing, decreasing, or divided into balanced halves at all times.
Adding a new element maintains the invariant by ejecting invalid elements (Monotonic Stack / Deque).

Technique 5: Subproblem Re-framing (Backwards / Complement Thinking)

Instead of finding items that match, find items that don't match and subtract from total.
Instead of searching from Start $\to$ End, search Backwards from End $\to$ Start (e.g. Pacific Atlantic Water Flow, Jump Game).

6. The 6-Step Problem Dissection Protocol

Follow this exact 5-minute protocol for every problem:

┌────────────────────────────────────────────────────────────────────────┐
│ STEP 1: Decode Constraints & Boundaries (1 min)                        │
│ • What is N? (Look up target Big-O in Cheat Matrix).                   │
│ • Are numbers positive/negative? Integers/floats? Strings/ASCII?       │
├────────────────────────────────────────────────────────────────────────┤
│ STEP 2: Identify Linguistic Signal Words (1 min)                       │
│ • Scan for triggers: "contiguous", "shortest", "kth", "all subsets".   │
│ • Match against the 25+ Keyword Rosetta Stone.                         │
├────────────────────────────────────────────────────────────────────────┤
│ STEP 3: Formulate Brute Force (30 secs)                                │
│ • Explain the obvious solution to the interviewer: "The brute force is  │
│   generating all subarrays in O(N^2)..."                               │
├────────────────────────────────────────────────────────────────────────┤
│ STEP 4: Optimize Bottleneck via Pattern Selection (1.5 mins)           │
│ • Apply Decision Tree to select data structure (Hash map, Monotonic    │
│   stack, Two Pointers, DP, Heap).                                      │
├────────────────────────────────────────────────────────────────────────┤
│ STEP 5: Define State Invariants & Edge Cases (1 min)                   │
│ • Trace edge cases: N = 0, N = 1, all duplicates, negative numbers.    │
├────────────────────────────────────────────────────────────────────────┤
│ STEP 6: Write Clean C++ Code & Step-by-Step Dry Run (Remaining Time)   │
└────────────────────────────────────────────────────────────────────────┘

7. 3 End-to-End Case Studies: Tracing Mental Reasoning

Let's see the framework in action on 3 realistic problems from scratch.

Case Study 1: "Capacity To Ship Packages Within D Days" (LeetCode #1011)

1. Problem Statement

Given an array weights and an integer days, return the least weight capacity of a ship that will result in all packages being shipped within days days in order.

2. Mental Dissection using Framework

Step 1 (Constraints): weights.length $\le 5 \times 10^4$. $N = 50,000 \implies$ Target time complexity must be $O(N)$ or $O(N \log N)$. $O(N^2)$ will Time Out.
Step 2 (Signal Words): "Find least weight capacity..." $\implies$ Optimization problem ("Minimize the maximum capacity").
Step 3 (Monotonic Check):
- If a capacity of $C = 15$ can ship all packages in $D$ days, can capacity $C = 16$ also do it? YES, always.
- If capacity $C = 10$ fails, will $C = 9$ also fail? YES, always.
- Monotonicity holds! $\implies$ Pattern: Binary Search on Answer Range.
Step 4 (Search Bounds):
- Lower bound low: $\max(\text{weights})$ (Ship must at least hold the single heaviest package).
- Upper bound high: $\sum \text{weights}$ (Ship can carry everything in 1 day).
Step 5 (Feasibility Function): Greedily load packages onto current day until capacity exceeded, then advance day. Takes $O(N)$ time.

3. Optimal C++ Code

#include <vector>
#include <numeric>
#include <algorithm>

class SolutionShipWithinDays {
private:
    bool canShip(const std::vector<int>& weights, int days, int capacity) {
        int daysNeeded = 1;
        int currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return daysNeeded <= days;
    }

public:
    int shipWithinDays(std::vector<int>& weights, int days) {
        int low = *std::max_element(weights.begin(), weights.end());
        int high = std::accumulate(weights.begin(), weights.end(), 0);
        int answer = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canShip(weights, days, mid)) {
                answer = mid;
                high = mid - 1; // Try to find smaller valid capacity
            } else {
                low = mid + 1; // Increase capacity
            }
        }
        return answer;
    }
};
// Time Complexity: O(N * log(Sum - Max)) = O(N log K)
// Space Complexity: O(1)

Case Study 2: "Subarray Sums Divisible by K" (LeetCode #974)

1. Problem Statement

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

2. Mental Dissection using Framework

Step 1 (Constraints): nums.length $\le 30,000$, contains negative numbers. $N = 30,000 \implies$ Target time: $O(N)$ or $O(N \log N)$.
Step 2 (Signal Words): "Contiguous subarray with sum divisible by K" $\implies$ Subarray Sum + Modulo Arithmetic.
Step 3 (Bottleneck in Brute Force): Generating all pairs $(i, j)$ and calculating sum is $O(N^2)$.
Step 4 (Mathematical Transformation):
- Let prefix sum up to index $i$ be $P[i]$.
- Subarray sum from $i$ to $j$ is $P[j] - P[i-1]$.
- Condition: $(P[j] - P[i-1]) \pmod k == 0 \iff P[j] \pmod k == P[i-1] \pmod k$.
- Pattern: Prefix Sum + Frequency Hash Map!
- Count how many previous prefix sums had the exact same remainder modulo $K$.
Step 5 (Handling Negative Modulo in C++):
- In C++, -7 % 5 = -2. Normalize to positive remainder: (rem % k + k) % k.

3. Optimal C++ Code

#include <vector>
#include <unordered_map>

int subarraysDivByK(std::vector<int>& nums, int k) {
    // Stores frequency of each remainder (0 to k - 1)
    std::vector<int> remainderFreq(k, 0);
    remainderFreq[0] = 1; // Prefix sum 0 has remainder 0 once
    
    int runningSum = 0;
    int count = 0;
    
    for (int x : nums) {
        runningSum += x;
        // Normalize negative modulo
        int remainder = ((runningSum % k) + k) % k;
        
        count += remainderFreq[remainder];
        remainderFreq[remainder]++;
    }
    
    return count;
}
// Time Complexity: O(N) single pass
// Space Complexity: O(K) for remainder vector

Case Study 3: "Reconstruct Itinerary" (LeetCode #332)

1. Problem Statement

Given a list of airline tickets [from, to], reconstruct the itinerary in order that uses all tickets once starting from "JFK". If multiple valid itineraries, return the one with smallest lexical order.

2. Mental Dissection using Framework

Step 1 (Signal Words): Directed graph with edges that must all be used exactly once.
Step 2 (Pattern Recognition):
- Visiting every vertex once = Hamiltonian Path ($NP$-hard).
- Visiting every EDGE once = Eulerian Path (Solvable in $O(E)$ via Hierholzer's Algorithm!).
Step 3 (Data Structure Selection):
- Directed graph with lexical order requirement $\implies$ std::unordered_map<string, std::priority_queue<string, vector<string>, greater<string>>> (Min-Heap adjacency list for automatic lexical ordering).
Step 4 (Algorithm Execution):
- Run DFS post-order traversal using Hierholzer's algorithm: traverse out-edges, push node to itinerary when it has no more outgoing edges, then reverse itinerary at the end.

3. Optimal C++ Code

#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

class SolutionReconstructItinerary {
private:
    std::unordered_map<std::string, std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>>> adj;
    std::vector<std::string> itinerary;

    void dfs(const std::string& airport) {
        auto& destinations = adj[airport];
        while (!destinations.empty()) {
            std::string nextAirport = destinations.top();
            destinations.pop(); // Consume edge
            dfs(nextAirport);
        }
        itinerary.push_back(airport); // Post-order append
    }

public:
    std::vector<std::string> findItinerary(std::vector<std::vector<std::string>>& tickets) {
        adj.clear();
        itinerary.clear();
        
        for (const auto& t : tickets) {
            adj[t[0]].push(t[1]);
        }
        
        dfs("JFK");
        std::reverse(itinerary.begin(), itinerary.end());
        return itinerary;
    }
};
// Time Complexity: O(E log E) due to lexical heap sorting
// Space Complexity: O(V + E)

8. The Deliberate Practice Protocol: How to Never Forget Patterns

To permanently imprint these patterns into your muscle memory:

1. The "3-Pass" Solving System

┌────────────────────────────────────────────────────────────────────────┐
│ PASS 1: Diagnostic Attempt (25 mins)                                   │
│ • Write down: 1) What are the signals? 2) Which pattern did I pick?    │
│ • If stuck after 25 mins: Read ONLY the pattern tag, NOT the solution. │
├────────────────────────────────────────────────────────────────────────┤
│ PASS 2: Template Synthesis (15 mins)                                   │
│ • After solving (or reading solution), implement from scratch without  │
│   looking at any reference.                                            │
├────────────────────────────────────────────────────────────────────────┤
│ PASS 3: Spaced Repetition Recall (3 Days & 14 Days Later)              │
│ • Redo the problem with an empty screen. If you solve it in under      │
│   15 mins, the pattern is permanently mastered.                        │
└────────────────────────────────────────────────────────────────────────┘

2. Pattern-Tagging Notes Template

Maintain a personal 1-page log for every problem you solve:

### [Problem Name / Number]
- **Signals Spotted**: [e.g. "Contiguous subarray", "N <= 10^5", "Positive numbers"]
- **Pattern Selected**: [e.g. "Variable Sliding Window"]
- **Why Brute Force Failed**: [e.g. "O(N^2) checks all subarrays"]
- **Key Invariant / Trick**: [e.g. "Shrink left when distinct count > k"]
- **Gotchas / Edge Cases**: [e.g. "Window size 0, single character string"]

00-how-to-solve-any-dsa-problem.md

Module 00: The Master Problem-Solving Engine & Pattern Recognition Framework

📑 Table of Contents

1. The Mindset Shift: Why Memorization Fails

2. The Grand Problem-to-Pattern Decision Tree (ASCII Engine)

3. The "Constraint $\to$ Target Big-O $\to$ Algorithm" Cheat Matrix

4. The 25+ Keyword & Linguistic Signal "Rosetta Stone"

5. The 5 Universal Problem-Solving Techniques

Technique 1: Bottleneck Analysis & Wasted Work Elimination

Technique 2: Binary Search on Answer Space (Monotonic Feasibility)

Technique 3: Preprocessing & Invariant Creation

Technique 4: Invariant Maintenance (Monotonic Structures)

Technique 5: Subproblem Re-framing (Backwards / Complement Thinking)

6. The 6-Step Problem Dissection Protocol

7. 3 End-to-End Case Studies: Tracing Mental Reasoning

Case Study 1: "Capacity To Ship Packages Within D Days" (LeetCode #1011)

1. Problem Statement

2. Mental Dissection using Framework

3. Optimal C++ Code

Case Study 2: "Subarray Sums Divisible by K" (LeetCode #974)

1. Problem Statement

2. Mental Dissection using Framework

3. Optimal C++ Code

Case Study 3: "Reconstruct Itinerary" (LeetCode #332)

1. Problem Statement

2. Mental Dissection using Framework

3. Optimal C++ Code

8. The Deliberate Practice Protocol: How to Never Forget Patterns

1. The "3-Pass" Solving System

2. Pattern-Tagging Notes Template