Pattern 04 of 22
Prefix Sum Pattern: Template + 157 LeetCode Problems
Precompute running totals once so any range query becomes a single subtraction.
- Easy
- 14
- Medium
- 102
- Hard
- 41
What the prefix sum pattern is
A prefix sum array stores the total of everything before each index, so the sum of any range is the difference of two entries and costs one subtraction no matter how long the range is. Building it is one pass; after that, a thousand range queries are a thousand subtractions instead of a thousand scans. The version that actually shows up in interviews is subtler: to count subarrays whose sum equals k, walk the array keeping the running total and a hash map of how many times each running total has been seen, because a subarray summing to k exists exactly where the current total minus k has appeared before. Seed that map with a zero total seen once, or every subarray that starts at index zero is missed. The same trick generalises past sums — replace the running total with a running parity, a running count difference, or a bitmask of seen characters, and the same map counts subarrays with equal ones and zeros, or with all characters appearing an even number of times.
When to use it
- Many range-sum queries are made over an array that does not change between them.
- You are counting subarrays whose sum, parity or balance hits a target.
- The brute force recomputes the sum of overlapping ranges from scratch.
- A two-dimensional version is needed: the same idea with inclusion-exclusion over four corners.
The prefix sum template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 157 problems listed below.
from collections import defaultdict
def count_subarrays_with_sum(nums, k):
counts = defaultdict(int)
counts[0] = 1 # the empty prefix, so a whole prefix can match
running = 0
total = 0
for value in nums:
running += value
total += counts[running - k] # every earlier prefix that closes a window
counts[running] += 1
return totalComplexity characteristics
- Time
- O(n) to build, O(1) per range query
- Auxiliary space
- O(n)
One pass builds the running totals; after that any range sum is a single subtraction, so k queries cost O(n + k) instead of O(n·k). The hash-map variant that counts subarrays hitting a target sum is a single O(n) pass with an O(n) map. The two-dimensional version costs O(r·c) to build and O(1) per rectangle query, using inclusion–exclusion over four corners.
Eyes only
Meet the prefix sum problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 157 prefix sum LeetCode problems
Every problem in the library the prefix sum pattern applies to, grouped by LeetCode's own difficulty rating. 139 of the 157 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (14)
Medium (102)
Hard (41)
Prefix Sum pattern FAQ
What is the prefix sum pattern?
A prefix sum array stores the total of everything before each index, so the sum of any range is the difference of two entries and costs one subtraction no matter how long the range is.
How many LeetCode problems use the prefix sum pattern?
This page lists 157 LeetCode problems that the prefix sum pattern applies to: 14 Easy, 102 Medium and 41 Hard. 139 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the prefix sum pattern?
O(n) to build, O(1) per range query time and O(n) space. One pass builds the running totals; after that any range sum is a single subtraction, so k queries cost O(n + k) instead of O(n·k). The hash-map variant that counts subarrays hitting a target sum is a single O(n) pass with an O(n) map. The two-dimensional version costs O(r·c) to build and O(1) per rectangle query, using inclusion–exclusion over four corners.
When should I use the prefix sum pattern in an interview?
Many range-sum queries are made over an array that does not change between them. You are counting subarrays whose sum, parity or balance hits a target.
Which prefix sum problem should I start with?
LeetCode 303. Range Sum Query - Immutable is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to prefix sum?
Hash Map, Sliding Window, Dynamic Programming, Two Pointers. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.