Recognizing Problem Categories - Identifying Problem Patterns | OneNoughtOne

Data Structures & AlgorithmsIdentifying Problem Patterns

Identifying Problem Patterns

LevelAdvanced

Duration90 mins

TopicIdentifying Problem Patterns

1 / 4

Recognizing Problem Categories

The Pattern Recognition Advantage

Consider two engineers facing the same algorithmic challenge. The first spends 45 minutes exploring dead ends, trying various approaches that don't quite fit, eventually arriving at a solution through trial and error. The second glances at the problem, recognizes its fundamental structure within seconds, and confidently implements a solution in 15 minutes.

What separates these two engineers isn't raw intelligence or years of experience alone—it's pattern recognition: the ability to see beneath the surface details of a problem and identify its fundamental category. This skill transforms problem-solving from a creative struggle into a structured exercise of recognition and application.

In this page, we'll develop the definitive framework for recognizing problem categories—the taxonomy that underlies virtually every algorithmic challenge you'll encounter in interviews, competitions, and production systems.

What You Will Learn

By the end of this page, you will understand the major categories of algorithmic problems, recognize the distinguishing characteristics of each category, and develop a systematic approach to classification that accelerates your problem-solving ability from the very first glance at a problem statement.

The Meta-Skill of Problem-Solving

Before diving into specific problem categories, we need to understand why categorization itself is so powerful—and why it's often the missing piece in a developer's problem-solving toolkit.

The cognitive science of expertise:

Research in cognitive psychology consistently demonstrates that expert performance in any domain—chess, medicine, software engineering—relies heavily on chunking: the ability to recognize complex patterns as single units. A chess grandmaster doesn't see 32 individual pieces; they see familiar configurations, attack patterns, and strategic structures.

Similarly, an expert algorithmist doesn't see a problem as a unique puzzle. They see it as an instance of a known category—a variation of the longest increasing subsequence, a graph coloring problem in disguise, or a classic two-pointer scenario with a twist. This recognition immediately narrows the solution space from infinite possibilities to a handful of known approaches.

The Expert's Internal Process

When experts solve problems quickly, they're not computing faster—they're recognizing rather than computing. They've seen this pattern before (or a close variant), and the solution approach comes as retrieval rather than invention. Your goal is to build this same library of recognizable patterns.

Why ad-hoc problem-solving fails at scale:

Without a categorical framework, every problem feels novel. You reinvent approaches, miss obvious connections to solved problems, and waste mental energy on structural questions that should be automatic. This approach might work for simple problems, but it becomes exhausting and error-prone as complexity increases.

Consider the difference:

Without categorization: "This problem asks me to find some kind of optimal path through choices... maybe I should try recursion? Or perhaps dynamic programming? Let me try both and see what works."
With categorization: "This is a shortest-path problem on an implicit graph where states are game configurations and edges are valid moves. Standard BFS will work since all edges have equal weight."

The second engineer isn't smarter—they've simply learned to see the problem's category, which immediately suggests the appropriate technique.

Benefits of Categorical Thinking

•Reduced cognitive load — Once you recognize the category, you stop considering irrelevant solution approaches and focus only on techniques that apply
•Faster convergence — Category recognition narrows the solution space immediately, reducing exploration time from exponential to linear
•Higher confidence — When you recognize a known pattern, you can be confident your approach will work before writing code
•Better communication — Categorical vocabulary lets you discuss problem structure precisely with other engineers
•Transferable intuition — Solving problems in one category builds intuition that transfers to all problems in that category

The Master Problem Taxonomy

While problems can be categorized in many ways, the most practical taxonomy organizes problems by their fundamental computational structure—the underlying abstract operations that define how solutions must work. This taxonomy cuts across application domains: whether a problem comes from finance, biology, gaming, or pure mathematics, its computational structure determines its category.

Here is the master taxonomy of algorithmic problem categories, organized from most common to specialized:

Master Problem Category Taxonomy
Category	Core Question	Typical Techniques	Frequency
Search & Lookup	Find an element or verify existence	Binary search, hash tables, BST, two-pointer	Very High
Traversal & Exploration	Visit all elements or states systematically	BFS, DFS, recursion, iteration	Very High
Optimization	Find the best solution among many	DP, greedy, binary search on answer	High
Counting & Enumeration	Count valid configurations or list all	DP counting, combinatorics, backtracking	High
Transformation & Construction	Build or modify a structure	In-place algorithms, constructive proofs	Medium
Aggregation & Query	Compute aggregate values over ranges	Prefix sums, segment trees, BIT	Medium
Partitioning & Grouping	Divide elements into valid groups	Union-Find, graph coloring, DFS/BFS	Medium
Ordering & Arrangement	Find or verify a valid ordering	Topological sort, sorting, permutation check	Medium
Matching & Pairing	Find optimal assignments between sets	Bipartite matching, greedy pairing	Lower
Simulation & State Machine	Model step-by-step state transitions	Direct simulation, automata	Lower

The hierarchical nature of categories:

These categories aren't mutually exclusive; they often nest within each other. An optimization problem might require traversal to explore the solution space. A counting problem might embed search subproblems. Understanding both the primary category and secondary elements is crucial for selecting the right approach.

Let's explore each major category in depth, understanding its defining characteristics and how to recognize it in the wild.

Category 1: Search & Lookup Problems

Defining question: Does a specific element exist, and if so, where?

Search problems are the most fundamental algorithmic category—finding whether something exists in a collection or locating its position. Despite their simplicity, search problems appear everywhere and form the building blocks of more complex categories.

Recognition Signals for Search Problems

•Keywords: "find", "locate", "exists", "contains", "search for", "lookup"
•Structure: A collection (array, tree, graph) and a target element or property
•Output type: Boolean (yes/no), index position, or the element itself
•Implicit searches: Many problems hide search as a subproblem—"find the minimum that satisfies..." is optimization + search

Subcategories of search problems:

Linear Search Variants

•Sequential scan — Check elements one by one when no ordering exists
•First/last occurrence — Find the first or last element matching a condition
•Conditional search — Find element satisfying a complex predicate
•Multi-target search — Find multiple elements in one pass

Binary Search Variants

•Classic binary search — Find exact match in sorted array
•Lower/upper bound — Find insertion point or first/last match
•Binary search on answer — Search solution space for optimal value
•Rotated/modified arrays — Binary search with structural variations

The Binary Search Recognition Pattern

Binary search applies whenever you have a monotonic predicate—a condition that transitions from false to true (or vice versa) at a single point across an ordered space. If you can answer "given value X, is the answer at least X?" and the answer changes from 'no' to 'yes' at some threshold, binary search applies. This insight unlocks binary search for optimization problems, not just sorted array lookups.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Problem: Find minimum number of days to ship all packages
// given weight limit per day. Classic binary search on answer.
 
function shipWithinDays(weights: number[], days: number): number {
    // We're searching for the minimum capacity that works
    // This is binary search on the answer space
    
    const canShipInDays = (capacity: number): boolean => {
        let daysNeeded = 1;
        let currentLoad = 0;
        
        for (const weight of weights) {
            if (currentLoad + weight > capacity) {
                daysNeeded++;
                currentLoad = weight;
            } else {
                currentLoad += weight;
            }
        }
        
        return daysNeeded <= days;
    };
    
    // Answer space: [max single weight, sum of all weights]
    let lo = Math.max(...weights);
    let hi = weights.reduce((a, b) => a + b, 0);
    
    // Binary search for minimum capacity that works
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (canShipInDays(mid)) {
            hi = mid;  // Try to find smaller valid capacity
        } else {
            lo = mid + 1;  // Need larger capacity
        }
    }
    
    return lo;
}

Category 2: Traversal & Exploration Problems

Defining question: How do we visit all relevant elements or explore all possible states?

Traversal problems require systematically visiting elements in a collection—whether it's tree nodes, graph vertices, matrix cells, or abstract state spaces. The key insight is that traversal problems are about coverage: ensuring you reach everything that needs to be processed.

Recognition Signals for Traversal Problems

•Keywords: "visit all", "explore", "traverse", "reach all", "path from X to Y"
•Structure: Graph-like data (explicit graphs, grids, trees, state machines)
•Output type: Path, whether something is reachable, visited node count, or transformed structure
•Constraint patterns: "connected components", "flood fill", "shortest path in unweighted graph"

The BFS vs DFS decision:

The choice between Breadth-First Search and Depth-First Search is one of the most common decisions in traversal problems. Here's a comprehensive guide:

BFS vs DFS: When to Use Each
Use Case	BFS	DFS
Shortest path (unweighted)	✓ Optimal—first path found is shortest	✗ May find longer paths first
Memory-constrained large graphs	✗ Stores entire frontier (O(width))	✓ Stack only holds current path (O(depth))
Finding any path quickly	Depends	✓ Often faster for sparse graphs
Level-order processing	✓ Natural level-by-level structure	✗ Mixes levels
Cycle detection in directed graphs	Possible but awkward	✓ Natural with back-edge detection
Topological sorting	✓ Kahn's algorithm	✓ Reverse postorder
State space exploration	✓ When solution is shallow	✓ When solution is deep
Maze solving / path finding	✓ Guarantees shortest path	✓ Faster for existence check

The Implicit Graph Pattern

Many traversal problems don't have explicit graphs. Instead, they define states and transitions: a chess position with possible moves, a string with allowed edits, a number with allowed operations. Recognizing these implicit graphs is crucial—once you see the graph structure, standard BFS/DFS applies directly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Problem: Transform "hit" to "cog" changing one letter at a time
// Each intermediate word must be in dictionary
// This is BFS on implicit graph where nodes are words, edges are single-letter changes
 
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
    
    // BFS on implicit graph
    const queue: [string, number][] = [[beginWord, 1]];
    const visited = new Set<string>([beginWord]);
    
    while (queue.length > 0) {
        const [word, distance] = queue.shift()!;
        
        if (word === endWord) return distance;
        
        // Generate all neighbors (words differing by one letter)
        for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) {  // 'a' to 'z'
                const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                
                if (wordSet.has(newWord) && !visited.has(newWord)) {
                    visited.add(newWord);
                    queue.push([newWord, distance + 1]);
                }
            }
        }
    }
    
    return 0;  // No path exists
}

Category 3: Optimization Problems

Defining question: Among all valid solutions, which is the best according to some criterion?

Optimization problems ask you to find maximum, minimum, or optimal values. They're among the most common interview problems because they naturally test both algorithmic knowledge and the ability to analyze tradeoffs.

Recognition Signals for Optimization Problems

•Keywords: "maximum", "minimum", "optimal", "best", "least cost", "most profit"
•Structure: A set of choices/options with associated values or costs
•Output type: A single optimal value, or the configuration that achieves it
•Constraint patterns: "subject to constraints", "without exceeding", "at least K"

The optimization technique decision tree:

Choosing the right optimization technique depends on problem structure. Here's a systematic approach:

Is there optimal substructure? (Optimal solution contains optimal sub-solutions)
├── NO → Consider exhaustive search, branch & bound, or approximation
└── YES → Does making locally optimal choices lead to global optimum?
    ├── YES → Use GREEDY algorithm
    │   Examples: Activity selection, Huffman coding, Dijkstra's
    └── NO → Are there overlapping subproblems?
        ├── YES → Use DYNAMIC PROGRAMMING
        │   Examples: Knapsack, LCS, Edit distance, Coin change
        └── NO → Use DIVIDE AND CONQUER
            Examples: Merge sort, Binary search, Closest pair
 
Special case: Can you binary search on the answer?
├── YES (monotonic feasibility) → BINARY SEARCH ON ANSWER
│   Examples: Capacity to ship, Minimum speed to arrive
└── NO → Proceed with above decision tree

The Greedy Trap

Many optimization problems look greedy but aren't. The 0/1 Knapsack problem is a classic example: taking the highest value-to-weight ratio items doesn't guarantee the optimal solution. Always verify that greedy works (ideally with a proof or exchange argument) before committing to it. When in doubt, DP is safer.

Greedy Works When...

•Greedy choice property holds: local optimal leads to global optimal
•You can prove exchange argument: swapping choices doesn't improve
•Problem has matroid structure (mathematical condition)
•Items can be fractionally selected (fractional knapsack)

DP Needed When...

•Choices interact: taking one affects what others are worth
•Problem has overlapping subproblems
•You need to consider combinations, not just individual selections
•Counter-examples exist for greedy approaches

Category 4: Counting & Enumeration Problems

Defining question: How many valid configurations exist, or what are all valid configurations?

Counting problems ask for the number of ways to achieve something. Enumeration problems ask you to list all valid solutions. These categories are closely related—enumeration is counting where you must produce each item, while counting can often use mathematical shortcuts.

Recognition Signals for Counting Problems

•Keywords: "how many", "count the number of", "in how many ways", "number of paths"
•Structure: A set of choices where order or selection matters
•Output type: A single count (often modulo 10^9+7), or a list of all items
•Constraint patterns: "subject to rules", "valid combinations", "distinct arrangements"

The counting technique decision:

Combinatorics formulas: When structure is regular and mathematical formulas apply (permutations, combinations, Catalan numbers)
DP counting: When structure requires tracking state across choices
Backtracking: When you need to enumerate all items, not just count them
Inclusion-exclusion: When counting by complement is easier than direct counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Problem: Count ways to climb n stairs, taking 1 to k steps at a time
// Classic counting problem with overlapping subproblems
 
function climbStairs(n: number, k: number): number {
    // dp[i] = number of ways to reach stair i
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;  // One way to stay at ground level
    
    for (let i = 1; i <= n; i++) {
        for (let step = 1; step <= Math.min(k, i); step++) {
            dp[i] += dp[i - step];
        }
    }
    
    return dp[n];
}
 
// For interview: mention optimization to O(k) space using sliding window
function climbStairsOptimized(n: number, k: number): number {
    const MOD = 1e9 + 7;
    const window: number[] = new Array(k).fill(0);
    window[0] = 1;  // dp[0] = 1
    let windowSum = 1;
    
    for (let i = 1; i <= n; i++) {
        const newVal = windowSum;
        const oldIdx = i % k;
        windowSum = (windowSum - window[oldIdx] + newVal + MOD) % MOD;
        window[oldIdx] = newVal;
    }
    
    return window[n % k];
}

The Modulo Signal

When a problem asks for the count "modulo 10^9+7" or similar, it's almost certainly a DP counting problem. The modulo is needed because the true count grows exponentially—too large for standard integers. This constraint is a strong category signal.

Additional Problem Categories

Beyond the four major categories above, several specialized categories appear regularly. Here's a brief overview of each with key recognition signals:

Transformation & Construction

•Question: Build X from Y, or convert X into valid form
•Signals: "construct", "rearrange", "transform", "make valid"
•Techniques: Constructive algorithms, greedy building, simulation
•Example: Build a valid parentheses string from given characters

Aggregation & Query

•Question: Compute aggregate values efficiently, often with updates
•Signals: "range sum", "range minimum", "update and query", "k-th element"
•Techniques: Prefix sums, segment trees, Fenwick trees, sparse tables
•Example: Answer 10^5 range sum queries with point updates

Partitioning & Grouping

•Question: Divide elements into groups satisfying constraints
•Signals: "group", "partition", "clusters", "connected components"
•Techniques: Union-Find, graph traversal, DFS forest
•Example: Find minimum groups such that no two elements in a group conflict

Ordering & Arrangement

•Question: Find a valid ordering or check if ordering is possible
•Signals: "dependencies", "before/after", "prerequisites", "topological"
•Techniques: Topological sort, sorting with custom comparators
•Example: Find order to take courses given prerequisite constraints

Matching & Pairing

•Question: Find optimal pairing between two sets
•Signals: "match", "assign", "pair", "bipartite"
•Techniques: Bipartite matching, Hungarian algorithm, greedy pairing
•Example: Assign students to projects maximizing total preference

Simulation & State Machine

•Question: Model a process step by step through defined transitions
•Signals: "simulate", "after K steps", "state transitions", "rules"
•Techniques: Direct simulation, cycle detection, matrix exponentiation
•Example: Simulate a game for 10^9 moves (requires cycle detection)

Cross-Category Patterns

Real problems rarely fit cleanly into a single category. Expert problem-solvers recognize when problems combine categories and apply hybrid approaches. Here are the most common combinations:

Common Category Combinations
Primary Category	Combined With	Example	Technique
Optimization	Search	Find minimum K such that X is possible	Binary search on answer + feasibility check
Optimization	Traversal	Shortest path in weighted graph	Dijkstra's algorithm (BFS + priority queue)
Counting	Optimization	Count paths with maximum score	DP with both count and max tracking
Enumeration	Optimization	Find all optimal solutions	Backtracking with pruning at optimal value
Traversal	Aggregation	Sum values from root to each node	DFS with running aggregate
Partitioning	Ordering	Divide into groups, order within each	Union-Find + topological sort per group

The Reduction Insight

Many advanced problems are solved by reducing them to known problems in different categories. "If I model X as a graph, this becomes shortest path." "If I think of states as nodes, this is BFS." Learning to see problems through multiple categorical lenses enables these powerful reductions.

Practical Recognition Framework

Here's a systematic approach to categorize any problem you encounter. Follow these steps to quickly narrow down the applicable category:

5-Step Category Recognition Process

•Read the question being asked: What does the problem actually want? A single value? A path? A count? All valid configurations? This immediately suggests a category.
•Identify the input structure: Is it a sequence (array, string)? A tree? A graph? A grid? The structure constrains which techniques apply.
•Note the constraints: Problem constraints encode hints. n ≤ 20 suggests exponential. n ≤ 10^5 suggests O(n log n). Modulo outputs suggest counting DP.
•Look for keywords: The vocabulary table above maps keywords to categories. "Maximum", "minimum" → optimization. "Count", "how many" → counting.
•Ask what happens as input scales: If finding one thing → search. If visiting everything → traversal. If picking from options → optimization/counting.

SEARCH & LOOKUP:
  "find", "exists", "contains", "locate", "search", "target"
 
TRAVERSAL & EXPLORATION:
  "visit", "reach", "path to", "connected", "reachable", "explore"
 
OPTIMIZATION:
  "maximum", "minimum", "optimal", "best", "largest", "smallest", "most", "least"
 
COUNTING & ENUMERATION:
  "how many", "count", "number of ways", "all possible", "generate all"
 
TRANSFORMATION:
  "convert", "transform", "rearrange", "build", "construct"
 
AGGREGATION:
  "range query", "sum between", "update and query", "k-th"
 
PARTITIONING:
  "group", "divide", "partition", "cluster", "components"
 
ORDERING:
  "valid order", "prerequisites", "dependencies", "sequence", "topological"
 
MATCHING:
  "pair", "match", "assign", "bipartite"
 
SIMULATION:
  "simulate", "after K steps", "evolve", "state machine"

Summary: Recognizing Problem Categories

We've established the foundational framework for recognizing problem categories—the first and most critical step in systematic problem-solving. Let's consolidate the key insights:

Key Takeaways

•Categorization is the meta-skill — Recognizing a problem's category immediately narrows the solution space and suggests appropriate techniques
•Ten major categories — Search, Traversal, Optimization, Counting, Transformation, Aggregation, Partitioning, Ordering, Matching, and Simulation cover virtually all problems
•Categories combine — Real problems often blend multiple categories; recognize both primary and secondary elements
•Keywords are signals — Problem vocabulary provides strong hints about category
•Constraints encode hints — Input size constraints suggest required time complexity, which suggests techniques
•Practice builds recognition — Each problem you solve adds to your pattern library, accelerating future recognition

What's next:

Now that we can recognize problem categories, the next page explores how to map these categories to appropriate data structures. The right data structure often makes the difference between an elegant O(n) solution and a struggling O(n²) attempt.

Page Complete

You now have a systematic framework for categorizing algorithmic problems. Practice applying this framework to new problems—within a few weeks of consistent practice, category recognition will become automatic.

1 / 4

Loading learning content...

Data Structures & AlgorithmsIdentifying Problem Patterns

Identifying Problem Patterns

LevelAdvanced

Duration90 mins

TopicIdentifying Problem Patterns

1 / 4

Recognizing Problem Categories

The Pattern Recognition Advantage

What You Will Learn

The Meta-Skill of Problem-Solving

Before diving into specific problem categories, we need to understand why categorization itself is so powerful—and why it's often the missing piece in a developer's problem-solving toolkit.

The cognitive science of expertise:

The Expert's Internal Process

Why ad-hoc problem-solving fails at scale:

Consider the difference:

Without categorization: "This problem asks me to find some kind of optimal path through choices... maybe I should try recursion? Or perhaps dynamic programming? Let me try both and see what works."
With categorization: "This is a shortest-path problem on an implicit graph where states are game configurations and edges are valid moves. Standard BFS will work since all edges have equal weight."

The second engineer isn't smarter—they've simply learned to see the problem's category, which immediately suggests the appropriate technique.

Benefits of Categorical Thinking

•Reduced cognitive load — Once you recognize the category, you stop considering irrelevant solution approaches and focus only on techniques that apply
•Faster convergence — Category recognition narrows the solution space immediately, reducing exploration time from exponential to linear
•Higher confidence — When you recognize a known pattern, you can be confident your approach will work before writing code
•Better communication — Categorical vocabulary lets you discuss problem structure precisely with other engineers
•Transferable intuition — Solving problems in one category builds intuition that transfers to all problems in that category

The Master Problem Taxonomy

Here is the master taxonomy of algorithmic problem categories, organized from most common to specialized:

Master Problem Category Taxonomy
Category	Core Question	Typical Techniques	Frequency
Search & Lookup	Find an element or verify existence	Binary search, hash tables, BST, two-pointer	Very High
Traversal & Exploration	Visit all elements or states systematically	BFS, DFS, recursion, iteration	Very High
Optimization	Find the best solution among many	DP, greedy, binary search on answer	High
Counting & Enumeration	Count valid configurations or list all	DP counting, combinatorics, backtracking	High
Transformation & Construction	Build or modify a structure	In-place algorithms, constructive proofs	Medium
Aggregation & Query	Compute aggregate values over ranges	Prefix sums, segment trees, BIT	Medium
Partitioning & Grouping	Divide elements into valid groups	Union-Find, graph coloring, DFS/BFS	Medium
Ordering & Arrangement	Find or verify a valid ordering	Topological sort, sorting, permutation check	Medium
Matching & Pairing	Find optimal assignments between sets	Bipartite matching, greedy pairing	Lower
Simulation & State Machine	Model step-by-step state transitions	Direct simulation, automata	Lower

The hierarchical nature of categories:

Let's explore each major category in depth, understanding its defining characteristics and how to recognize it in the wild.

Category 1: Search & Lookup Problems

Defining question: Does a specific element exist, and if so, where?

Recognition Signals for Search Problems

•Keywords: "find", "locate", "exists", "contains", "search for", "lookup"
•Structure: A collection (array, tree, graph) and a target element or property
•Output type: Boolean (yes/no), index position, or the element itself
•Implicit searches: Many problems hide search as a subproblem—"find the minimum that satisfies..." is optimization + search

Subcategories of search problems:

Linear Search Variants

•Sequential scan — Check elements one by one when no ordering exists
•First/last occurrence — Find the first or last element matching a condition
•Conditional search — Find element satisfying a complex predicate
•Multi-target search — Find multiple elements in one pass

Binary Search Variants

•Classic binary search — Find exact match in sorted array
•Lower/upper bound — Find insertion point or first/last match
•Binary search on answer — Search solution space for optimal value
•Rotated/modified arrays — Binary search with structural variations

The Binary Search Recognition Pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Problem: Find minimum number of days to ship all packages
// given weight limit per day. Classic binary search on answer.
 
function shipWithinDays(weights: number[], days: number): number {
    // We're searching for the minimum capacity that works
    // This is binary search on the answer space
    
    const canShipInDays = (capacity: number): boolean => {
        let daysNeeded = 1;
        let currentLoad = 0;
        
        for (const weight of weights) {
            if (currentLoad + weight > capacity) {
                daysNeeded++;
                currentLoad = weight;
            } else {
                currentLoad += weight;
            }
        }
        
        return daysNeeded <= days;
    };
    
    // Answer space: [max single weight, sum of all weights]
    let lo = Math.max(...weights);
    let hi = weights.reduce((a, b) => a + b, 0);
    
    // Binary search for minimum capacity that works
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (canShipInDays(mid)) {
            hi = mid;  // Try to find smaller valid capacity
        } else {
            lo = mid + 1;  // Need larger capacity
        }
    }
    
    return lo;
}

Category 2: Traversal & Exploration Problems

Defining question: How do we visit all relevant elements or explore all possible states?

Recognition Signals for Traversal Problems

•Keywords: "visit all", "explore", "traverse", "reach all", "path from X to Y"
•Structure: Graph-like data (explicit graphs, grids, trees, state machines)
•Output type: Path, whether something is reachable, visited node count, or transformed structure
•Constraint patterns: "connected components", "flood fill", "shortest path in unweighted graph"

The BFS vs DFS decision:

The choice between Breadth-First Search and Depth-First Search is one of the most common decisions in traversal problems. Here's a comprehensive guide:

BFS vs DFS: When to Use Each
Use Case	BFS	DFS
Shortest path (unweighted)	✓ Optimal—first path found is shortest	✗ May find longer paths first
Memory-constrained large graphs	✗ Stores entire frontier (O(width))	✓ Stack only holds current path (O(depth))
Finding any path quickly	Depends	✓ Often faster for sparse graphs
Level-order processing	✓ Natural level-by-level structure	✗ Mixes levels
Cycle detection in directed graphs	Possible but awkward	✓ Natural with back-edge detection
Topological sorting	✓ Kahn's algorithm	✓ Reverse postorder
State space exploration	✓ When solution is shallow	✓ When solution is deep
Maze solving / path finding	✓ Guarantees shortest path	✓ Faster for existence check

The Implicit Graph Pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Problem: Transform "hit" to "cog" changing one letter at a time
// Each intermediate word must be in dictionary
// This is BFS on implicit graph where nodes are words, edges are single-letter changes
 
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
    
    // BFS on implicit graph
    const queue: [string, number][] = [[beginWord, 1]];
    const visited = new Set<string>([beginWord]);
    
    while (queue.length > 0) {
        const [word, distance] = queue.shift()!;
        
        if (word === endWord) return distance;
        
        // Generate all neighbors (words differing by one letter)
        for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) {  // 'a' to 'z'
                const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                
                if (wordSet.has(newWord) && !visited.has(newWord)) {
                    visited.add(newWord);
                    queue.push([newWord, distance + 1]);
                }
            }
        }
    }
    
    return 0;  // No path exists
}

Category 3: Optimization Problems

Defining question: Among all valid solutions, which is the best according to some criterion?

Recognition Signals for Optimization Problems

•Keywords: "maximum", "minimum", "optimal", "best", "least cost", "most profit"
•Structure: A set of choices/options with associated values or costs
•Output type: A single optimal value, or the configuration that achieves it
•Constraint patterns: "subject to constraints", "without exceeding", "at least K"

The optimization technique decision tree:

Choosing the right optimization technique depends on problem structure. Here's a systematic approach:

Is there optimal substructure? (Optimal solution contains optimal sub-solutions)
├── NO → Consider exhaustive search, branch & bound, or approximation
└── YES → Does making locally optimal choices lead to global optimum?
    ├── YES → Use GREEDY algorithm
    │   Examples: Activity selection, Huffman coding, Dijkstra's
    └── NO → Are there overlapping subproblems?
        ├── YES → Use DYNAMIC PROGRAMMING
        │   Examples: Knapsack, LCS, Edit distance, Coin change
        └── NO → Use DIVIDE AND CONQUER
            Examples: Merge sort, Binary search, Closest pair
 
Special case: Can you binary search on the answer?
├── YES (monotonic feasibility) → BINARY SEARCH ON ANSWER
│   Examples: Capacity to ship, Minimum speed to arrive
└── NO → Proceed with above decision tree

The Greedy Trap

Greedy Works When...

•Greedy choice property holds: local optimal leads to global optimal
•You can prove exchange argument: swapping choices doesn't improve
•Problem has matroid structure (mathematical condition)
•Items can be fractionally selected (fractional knapsack)

DP Needed When...

•Choices interact: taking one affects what others are worth
•Problem has overlapping subproblems
•You need to consider combinations, not just individual selections
•Counter-examples exist for greedy approaches

Category 4: Counting & Enumeration Problems

Defining question: How many valid configurations exist, or what are all valid configurations?

Recognition Signals for Counting Problems

•Keywords: "how many", "count the number of", "in how many ways", "number of paths"
•Structure: A set of choices where order or selection matters
•Output type: A single count (often modulo 10^9+7), or a list of all items
•Constraint patterns: "subject to rules", "valid combinations", "distinct arrangements"

The counting technique decision:

Combinatorics formulas: When structure is regular and mathematical formulas apply (permutations, combinations, Catalan numbers)
DP counting: When structure requires tracking state across choices
Backtracking: When you need to enumerate all items, not just count them
Inclusion-exclusion: When counting by complement is easier than direct counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Problem: Count ways to climb n stairs, taking 1 to k steps at a time
// Classic counting problem with overlapping subproblems
 
function climbStairs(n: number, k: number): number {
    // dp[i] = number of ways to reach stair i
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;  // One way to stay at ground level
    
    for (let i = 1; i <= n; i++) {
        for (let step = 1; step <= Math.min(k, i); step++) {
            dp[i] += dp[i - step];
        }
    }
    
    return dp[n];
}
 
// For interview: mention optimization to O(k) space using sliding window
function climbStairsOptimized(n: number, k: number): number {
    const MOD = 1e9 + 7;
    const window: number[] = new Array(k).fill(0);
    window[0] = 1;  // dp[0] = 1
    let windowSum = 1;
    
    for (let i = 1; i <= n; i++) {
        const newVal = windowSum;
        const oldIdx = i % k;
        windowSum = (windowSum - window[oldIdx] + newVal + MOD) % MOD;
        window[oldIdx] = newVal;
    }
    
    return window[n % k];
}

The Modulo Signal

Additional Problem Categories

Beyond the four major categories above, several specialized categories appear regularly. Here's a brief overview of each with key recognition signals:

Transformation & Construction

•Question: Build X from Y, or convert X into valid form
•Signals: "construct", "rearrange", "transform", "make valid"
•Techniques: Constructive algorithms, greedy building, simulation
•Example: Build a valid parentheses string from given characters

Aggregation & Query

•Question: Compute aggregate values efficiently, often with updates
•Signals: "range sum", "range minimum", "update and query", "k-th element"
•Techniques: Prefix sums, segment trees, Fenwick trees, sparse tables
•Example: Answer 10^5 range sum queries with point updates

Partitioning & Grouping

•Question: Divide elements into groups satisfying constraints
•Signals: "group", "partition", "clusters", "connected components"
•Techniques: Union-Find, graph traversal, DFS forest
•Example: Find minimum groups such that no two elements in a group conflict

Ordering & Arrangement

•Question: Find a valid ordering or check if ordering is possible
•Signals: "dependencies", "before/after", "prerequisites", "topological"
•Techniques: Topological sort, sorting with custom comparators
•Example: Find order to take courses given prerequisite constraints

Matching & Pairing

•Question: Find optimal pairing between two sets
•Signals: "match", "assign", "pair", "bipartite"
•Techniques: Bipartite matching, Hungarian algorithm, greedy pairing
•Example: Assign students to projects maximizing total preference

Simulation & State Machine

•Question: Model a process step by step through defined transitions
•Signals: "simulate", "after K steps", "state transitions", "rules"
•Techniques: Direct simulation, cycle detection, matrix exponentiation
•Example: Simulate a game for 10^9 moves (requires cycle detection)

Cross-Category Patterns

Real problems rarely fit cleanly into a single category. Expert problem-solvers recognize when problems combine categories and apply hybrid approaches. Here are the most common combinations:

Common Category Combinations
Primary Category	Combined With	Example	Technique
Optimization	Search	Find minimum K such that X is possible	Binary search on answer + feasibility check
Optimization	Traversal	Shortest path in weighted graph	Dijkstra's algorithm (BFS + priority queue)
Counting	Optimization	Count paths with maximum score	DP with both count and max tracking
Enumeration	Optimization	Find all optimal solutions	Backtracking with pruning at optimal value
Traversal	Aggregation	Sum values from root to each node	DFS with running aggregate
Partitioning	Ordering	Divide into groups, order within each	Union-Find + topological sort per group

The Reduction Insight

Practical Recognition Framework

Here's a systematic approach to categorize any problem you encounter. Follow these steps to quickly narrow down the applicable category:

5-Step Category Recognition Process

•Read the question being asked: What does the problem actually want? A single value? A path? A count? All valid configurations? This immediately suggests a category.
•Identify the input structure: Is it a sequence (array, string)? A tree? A graph? A grid? The structure constrains which techniques apply.
•Note the constraints: Problem constraints encode hints. n ≤ 20 suggests exponential. n ≤ 10^5 suggests O(n log n). Modulo outputs suggest counting DP.
•Look for keywords: The vocabulary table above maps keywords to categories. "Maximum", "minimum" → optimization. "Count", "how many" → counting.
•Ask what happens as input scales: If finding one thing → search. If visiting everything → traversal. If picking from options → optimization/counting.

SEARCH & LOOKUP:
  "find", "exists", "contains", "locate", "search", "target"
 
TRAVERSAL & EXPLORATION:
  "visit", "reach", "path to", "connected", "reachable", "explore"
 
OPTIMIZATION:
  "maximum", "minimum", "optimal", "best", "largest", "smallest", "most", "least"
 
COUNTING & ENUMERATION:
  "how many", "count", "number of ways", "all possible", "generate all"
 
TRANSFORMATION:
  "convert", "transform", "rearrange", "build", "construct"
 
AGGREGATION:
  "range query", "sum between", "update and query", "k-th"
 
PARTITIONING:
  "group", "divide", "partition", "cluster", "components"
 
ORDERING:
  "valid order", "prerequisites", "dependencies", "sequence", "topological"
 
MATCHING:
  "pair", "match", "assign", "bipartite"
 
SIMULATION:
  "simulate", "after K steps", "evolve", "state machine"

Summary: Recognizing Problem Categories

We've established the foundational framework for recognizing problem categories—the first and most critical step in systematic problem-solving. Let's consolidate the key insights:

Key Takeaways

•Categorization is the meta-skill — Recognizing a problem's category immediately narrows the solution space and suggests appropriate techniques
•Ten major categories — Search, Traversal, Optimization, Counting, Transformation, Aggregation, Partitioning, Ordering, Matching, and Simulation cover virtually all problems
•Categories combine — Real problems often blend multiple categories; recognize both primary and secondary elements
•Keywords are signals — Problem vocabulary provides strong hints about category
•Constraints encode hints — Input size constraints suggest required time complexity, which suggests techniques
•Practice builds recognition — Each problem you solve adds to your pattern library, accelerating future recognition

What's next:

Page Complete

1 / 4