6. Prefix Sum
Precompute running totals so range questions become O(1).
Your progress0 of 12
4easy
7medium
1hard
Understand the topic
A prefix sum is a running total: prefix[i] = sum of the first i numbers. Once you have it, the sum of any range is one subtraction: sum(l..r) = prefix[r+1] - prefix[l].
Three ideas build on that. Store prefix sums in a HashMap to count subarrays with a target sum. Use a difference array to add to whole ranges in O(1). Use a 2D prefix sum for rectangles in a matrix.
| # | Problem | Pattern | Level | ||
|---|---|---|---|---|---|
| 1 | Find the Highest Altitude #1732 | Running sum | Easy | LeetCode ↗ | |
| 2 | Range Sum Query - Immutable #303 | Prefix array | Easy | LeetCode ↗ | |
| 3 | Find Pivot Index #724 | Total minus left | Easy | LeetCode ↗ | |
| 4 | Left and Right Sum Differences #2574 | Prefix & suffix | Easy | LeetCode ↗ | |
| 5 | Product of Array Except Self #238 | Prefix & suffix products | Medium | LeetCode ↗ | |
| 6 | Range Sum Query 2D - Immutable #304 | 2D prefix sum | Medium | LeetCode ↗ | |
| 7 | Subarray Sum Equals K #560 | Prefix sum + HashMap | Medium | LeetCode ↗ | |
| 8 | Contiguous Array #525 | Prefix sum + first index | Medium | LeetCode ↗ | |
| 9 | Subarray Sums Divisible by K #974 | Prefix remainders | Medium | LeetCode ↗ | |
| 10 | Continuous Subarray Sum #523 | Prefix remainders + index | Medium | LeetCode ↗ | |
| 11 | Corporate Flight Bookings #1109 | Difference array | Medium | LeetCode ↗ | |
| 12 | Number of Submatrices That Sum to Target #1074 | 2D → 1D prefix + HashMap | Hard | LeetCode ↗ |
Nothing matches that filter.
Work top to bottom — each list goes from easy to hard. Try a problem for at least 15 minutes before opening a hint. Ticks are saved in your browser.