Prefix Sum Patterns for LeetCode Beginners

You see "count subarrays" or "find longest subarray with..." and wonder if it's sliding window or something else. Prefix sums quietly solve many of these by converting range queries into simple arithmetic.

TL;DR

• Prefix sums turn any contiguous range query into a subtraction: prefix[r] - prefix[l-1].
• They matter for interviews because they avoid nested loops on sums, counts, and balances.
• Core steps: build a running array, use subtraction to query ranges, add a hash map when counts or earliest indices matter.
• Beginners trip on index offsets (starting at 0 vs 1) and forget to initialize the map with 0.
• You'll learn when prefix sums beat sliding windows, how to sketch a quick diagram, and a reusable TypeScript helper.

Beginner-Friendly Explanation

A prefix sum is the cumulative total up to each index. Once you precompute it, any subarray sum is one subtraction away. That means you no longer loop twice; you reuse the stored totals.

Think of walking a trail with mile markers. The distance between mile 2 and mile 7 is just 'marker[7] - marker[2]'—no need to recount every step.

Step-by-Step Learning Guidance

1) Build the Running Array

• Start with prefix[0] = 0 so subtraction works cleanly.
• For each i, set prefix[i + 1] = prefix[i] + nums[i].

2) Answer Range Queries Fast

• Sum of nums[l..r] is prefix[r + 1] - prefix[l].
• Memorize the +1 on r and no offset on l to avoid off-by-one.

3) Add a Hash Map for Counts

• For "number of subarrays with sum K": store how many times each prefix value has appeared.
• As you walk through prefix[i], look for prefix[i] - K in the map to count valid starts.

4) Decide When Not to Use Sliding Window

• If values can be negative, sliding window invariants break; prefix + hash map stays stable.
• If the query is "exactly K" rather than "at most K", prefix sums handle it cleanly.

5) Present the Approach Aloud

• In an interview, say: "I'll precompute prefix sums to answer any subarray sum in O(1), then use a frequency map to count how many prefixes differ by K." For more interview prep guidance, see how to explain your thought process during coding interviews.

Visualizable Example: Counting Subarrays with Sum = 3

nums: [1, 2, -1, 2]
prefix (1-based): [0, 1, 3, 2, 4]

Walk the prefixes:

• At prefix 1: value 1. Need 1 - 3 = -2 → 0 matches.
• At prefix 2: value 3. Need 0 → 1 match (the empty start), so +1 subarray.
• At prefix 3: value 2. Need -1 → 0 matches.
• At prefix 4: value 4. Need 1 → matches prefix at index 1 → +1 subarray.

Total = 2 subarrays ('[1,2]' and '[2,-1,2]'). A simple table like this is easy to sketch during an interview.

Practical Preparation Strategies

Use a Reusable Helper

Create a small helper to generate prefixes so you stop rewriting loops.

Rehearse Edge Cases

• Empty prefix (sum 0) must be in the map once.
• Single-element arrays with target equal to that element.
• Negative numbers that break window-based approaches.

Pair With Structured Practice

• Solve 3-4 problems that vary only by target type (sum, balance, modulo). For more prefix sum guidance, see prefix sum technique on LeetCode for beginners.
• Keep a one-page cheat sheet of the subtraction formula and the initialization rule.

Common Mistakes to Avoid

Misaligned Offsets

Building prefix the same length as nums makes prefix[r] - prefix[l] ambiguous. Always allocate one extra slot and start at 0.

Forgetting the Initial Zero

If the map lacks 0: 1, subarrays starting at index 0 are missed.

Mixing Up Kinds of Queries

Prefix sums answer contiguous questions. They don't help with subsets or k-th element queries—use other patterns there.

Code Example: Count Subarrays with Target Sum

function countSubarrays(nums: number[], target: number): number {
  const freq = new Map<number, number>();
  freq.set(0, 1); // empty prefix

  let prefix = 0;
  let total = 0;

  for (const num of nums) {
    prefix += num;
    const need = prefix - target;
    total += freq.get(need) ?? 0;
    freq.set(prefix, (freq.get(prefix) ?? 0) + 1);
  }

  return total;
}

Each step maintains the running sum and counts how many earlier prefixes make the current one differ by target. Tools like LeetCopilot can overlay this map while you iterate, reducing guesswork.

FAQ

How do I know a problem fits prefix sums?
If the task is "sum/count of a contiguous range" and sliding window struggles with negatives or exact sums, prefix sums are a good fit.

What should I practice first?
Start with fixed-target sums, then move to balance problems (e.g., equal zeros and ones) and modulo variants.

Is this important for interviews?
Yes—prefix sums show up in arrays, strings, and even grids (2D prefix). Interviewers like them because they show planning before coding.

Do I need 1-based or 0-based prefixes?
Use 1-based (extra slot) to keep the subtraction clean. Just be consistent through the solution.

Conclusion

Prefix sums are a structured way to tame contiguous range questions: precompute once, subtract precisely, and initialize correctly. Pair deliberate sketches with careful offset handling, and you'll handle subarray queries confidently, even under interview pressure.