← All patterns
4 / 32
Scanning & Windows

Prefix Sum

When you see it

Signal words

If the prompt uses any of these, this pattern should come to mind first.

range sumsubarray sum equals kcount of subarrayscumulativebetween i and j
Practice

Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.

Ask yourself

  1. Repeated range-sum / range-count queries?
  2. “Subarray summing to K” — pair with a hashmap of prefixes.
  3. Can a difference of two prefixes give the answer in O(1)?

Classic problem

Range Sum Query (LeetCode 303) — Precompute prefix sums so any range query sum(i, j) runs in O(1): pre[j] - pre[i-1].

Input: nums = [3, 1, 4, 1, 5, 2], query sum(1, 4)

Output: 11 — pre[4] - pre[0] = 14 - 3 = 11 (sum of elements at indices 1 through 4).

Watch it run

Common pitfalls

Forgetting the seed prefix {0: 1} for subarrays starting at index 0.

Off-by-one between inclusive/exclusive prefix arrays.