Identifying Problem Patterns

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

R - RECOGNIZE: Before solving, explicitly identify the pattern
    - Read problem statement completely
    - List all problem characteristics (input type, output type, constraints)
    - Hypothesize which categories the problem might belong to
    - Note what signals led to your hypothesis
    
A - ATTEMPT: Try your approach based on pattern recognition
    - If pattern suggests a specific technique, outline that approach
    - Don't code immediately—sketch the solution structure first
    - Identify potential issues with your approach
    
P - PROCESS: Whether successful or not, extract learnings
    - What worked? What didn't?
    - If your pattern guess was wrong, why?
    - What signals did you miss or misinterpret?
    
I - INDEX: Add to your pattern library
    - Record the problem, your approach, and key insights
    - Note distinguishing features that signal this pattern
    - Link to similar problems you've solved
    
D - DRILL: Reinforce through spaced repetition
    - Revisit the problem after 1 day, 1 week, 1 month
    - Focus on rapid recognition, not re-solving
    - Quiz yourself: "What pattern? What technique? Why?"

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

PATTERN NAME: [Descriptive name]
CATEGORY: [Problem category from our taxonomy]
 
RECOGNITION SIGNALS:
- [Signal 1: What in the problem statement suggests this pattern?]
- [Signal 2: What constraints hint at this pattern?]
- [Signal 3: What keywords appear?]
 
CORE TECHNIQUE:
- [Algorithm or approach]
- [Key data structures]
- [Time/space complexity]
 
TEMPLATE CODE:
[Skeleton code that applies to all problems of this type]
 
VARIATIONS:
- [Variation 1: How does the pattern adapt?]
- [Variation 2: What modifications are common?]
 
EXAMPLE PROBLEMS:
1. [Problem name] - [Why it fits this pattern]
2. [Problem name] - [Why it fits this pattern]
3. [Problem name] - [Why it fits this pattern]
 
COMMON MISTAKES:
- [Mistake 1: What traps exist?]
- [Mistake 2: Off-by-one errors, edge cases?]
 
RELATED PATTERNS:
- [Pattern that's easily confused with this one]
- [Pattern that often combines with this one]

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

// Problem: Given an array of integers and a target sum,
// find the number of continuous subarrays whose sum equals target.
// Constraints: n ≤ 20,000
 
// 30-SECOND ANALYSIS:
// 
// Keywords: "continuous subarrays", "sum equals"
// Category: Aggregation / Counting
// Signal: "subarray sum" → Prefix Sum pattern
// 
// Data Structure: Hash Map (to store prefix sum frequencies)
// Algorithm: Prefix Sum + Hash Map counting
// Complexity: O(n) time, O(n) space
//
// Recognition: If we've seen prefix_sum - target before,
//              those positions are the starts of valid subarrays
 
function subarraySum(nums: number[], k: number): number {
    const counts = new Map<number, number>();
    counts.set(0, 1);  // Empty prefix sum
    
    let prefixSum = 0;
    let result = 0;
    
    for (const num of nums) {
        prefixSum += num;
        
        // If prefixSum - k exists, we found valid subarray(s)
        result += counts.get(prefixSum - k) || 0;
        
        counts.set(prefixSum, (counts.get(prefixSum) || 0) + 1);
    }
    
    return result;
}
 
// Pattern recognized: Prefix Sum + Hash Map for subarray sum counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

After failing to solve a problem or solving incorrectly:
 
1. IMMEDIATE ANALYSIS (within 1 hour)
   □ What pattern was actually needed?
   □ Did I consider this pattern? If not, why not?
   □ What signals pointed to this pattern that I missed?
   □ If I considered it but rejected it, what was my reasoning?
   □ Was my reasoning flawed, or was the signal genuinely weak?
 
2. COMPARE TO PAST
   □ Have I solved similar problems before?
   □ If yes, why didn't I make the connection?
   □ If no, this is a new pattern—add to library
 
3. EXTRACT THE LESSON
   □ Write a specific "next time I see X, I'll consider Y" rule
   □ Identify the distinguishing signal I should have noticed
   □ Create a flashcard with this signal
 
4. SCHEDULE REINFORCEMENT
   □ Add similar problems to practice queue
   □ Review this problem again in 1 day, 1 week, 1 month
   □ Practice the pattern until it's automatic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

PROBLEM: Given a string, find the length of the longest substring 
without repeating characters.
 
RECOGNITION PROCESS (should be ~10 seconds):
 
Keywords spotted: "substring", "longest"
→ This signals SLIDING WINDOW
 
Additional signal: "without repeating"
→ Need to track element frequency
→ SLIDING WINDOW + HASH SET/MAP
 
Constraint check: String length ≤ 50,000
→ O(n) or O(n log n) needed
→ Sliding window gives O(n) ✓
 
PATTERN IDENTIFIED: Variable Sliding Window
TECHNIQUE: Expand right pointer, contract left when duplicate found
DATA STRUCTURE: Hash Set for character tracking
COMPLEXITY: O(n) time, O(min(n, alphabet)) space
 
Time to recognition: ~10 seconds
Time to outline solution: ~30 seconds
Total before coding: ~40 seconds

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

PROBLEM: There are n courses. Some courses have prerequisites.
Determine if it's possible to finish all courses.
 
RECOGNITION PROCESS:
 
Keywords spotted: "prerequisites", "courses"
→ This is ordering with dependencies
→ Signals GRAPH + TOPOLOGICAL SORT
 
Problem structure: Can we find valid ordering?
→ Topological sort possible only if NO CYCLES
 
Constraint check: n ≤ 2000, edges ≤ 5000
→ Graph traversal O(V + E) is fine
 
PATTERN IDENTIFIED: Topological Sort / Cycle Detection
TECHNIQUE: 
  - Build adjacency list from prerequisites
  - Either Kahn's algorithm (BFS) or DFS with coloring
  - If all nodes processed, answer is YES
DATA STRUCTURE: Adjacency list, visited array (or in-degree array)
COMPLEXITY: O(V + E) time, O(V + E) space
 
Additional insight: This is the classic "can we topologically sort?" question
 
Time to recognition: ~5 seconds (very common 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

PROBLEM: Find the contiguous subarray with the largest product.
 
RECOGNITION PROCESS:
 
Keywords spotted: "contiguous subarray", "largest"
→ Initial guess: Sliding window? Kadane's algorithm?
 
Deeper analysis: Product, not sum
→ Negative numbers change everything
→ A large negative × negative = large positive
→ Can't use standard Kadane directly
 
Key insight: Need to track both MAX and MIN ending at each position
→ This is a MODIFIED KADANE (Linear DP)
 
PATTERN IDENTIFIED: Linear DP (modified Kadane)
TECHNIQUE:
  - Track maxEndingHere and minEndingHere
  - At each step: new element could use +max, +min, or start fresh
  - maxEndingHere = max(nums[i], maxEndingHere * nums[i], minEndingHere * nums[i])
DATA STRUCTURE: Just variables for current max/min
COMPLEXITY: O(n) time, O(1) space
 
Why not standard sliding window? 
- No clear "shrink" condition
- Need to consider all positions as potential starts
 
Time to recognition: ~20 seconds (requires deeper analysis)