Prefix Sum Pattern Recognition: Spot It in 10 Seconds

You have 45 minutes to solve 2 LeetCode problems in an interview. You can't afford to waste 10 minutes figuring out which pattern to use.

You need to recognize prefix sum problems in seconds.

TL;DR

Keyword triggers:

• "Range sum"
• "Subarray sum"
• "Cumulative"
• "Multiple queries"

Problem patterns:

• Range queries → Prefix sum
• Subarray with target sum → Prefix sum + hash map
• Matrix range → 2D prefix sum
• Range updates → Difference array

Keyword Triggers

"Range Sum"

→ Prefix sum (almost always)

Example: "Calculate sum from index i to j"

"Subarray Sum"

→ Prefix sum + hash map

Example: "Count subarrays with sum equal to k"

"Cumulative"

→ Prefix sum

Example: "Running total" or "cumulative sum"

"Multiple Queries"

→ Prefix sum (preprocess once, query many)

The 10-Second Checklist

1. See "range" or "subarray"? → Consider prefix sum
2. Multiple queries? → Prefix sum
3. Exact target sum? → Prefix sum + hash map
4. Matrix? → 2D prefix sum
5. Updates? → Difference array

Decision Tree

"Subarray" in problem?
  → YES: Prefix sum likely
  → NO: Check other patterns

Exact target sum?
  → YES: Prefix sum + hash map
  → NO: Check if longest/shortest

Multiple queries?
  → YES: Prefix sum
  → NO: Might be sliding window

Example Problem Breakdown

Problem 1: "Given an array, answer q queries: sum from index i to j"

• Keywords: "range", "queries"
• Pattern: Prefix sum ✓

Problem 2: "Count subarrays with sum equal to k"

• Keywords: "subarray", "sum equal to"
• Pattern: Prefix sum + hash map ✓

Problem 3: "Find longest subarray with sum ≤ k (all positive)"

• Keywords: "longest", "positive"
• Pattern: Sliding window (not prefix sum!)

Practice

Train yourself to recognize patterns instantly:

1. Read problem title
2. Identify keywords
3. Choose pattern in 10 seconds
4. Verify with first example

Conclusion

Key takeaway: Keywords + problem type → Pattern choice

For more, see the complete guide and vs Sliding Window.