Welcome to our next lesson in Algorithmic Foundations. In our previous session, we explored the sliding window pattern, an excellent tool for finding an optimal contiguous subarray that meets a certain criteria. Today, we'll examine a different but equally powerful technique for array problems: the prefix sum.
While a sliding window dynamically adjusts its size to find a "best" segment, the prefix sum technique focuses on answering queries about fixed ranges with maximum efficiency. Specifically, this lesson will teach you how to apply the prefix sum technique to solve range query problems. We will cover the fundamental 1D case, extend it to 2D matrices, and tackle a common interview problem that combines prefix sums with hash maps to solve a seemingly complex challenge in linear time.
The Problem: Repeated Range Sum Queries
Imagine you are given a static array of numbers and need to answer many questions, each asking for the sum of elements within a specific range, say from index i to j.
The naive approach is straightforward: for each query, you would loop from i to j and add up the numbers. If you have Q queries and the array has N elements, the worst-case time complexity could be . For a large array and many queries—a common scenario in backend systems processing analytics or in coding challenges—this is far too slow.
The prefix sum technique offers a classic trade-off: we perform a one-time pre-computation to enable answering each subsequent query in constant time, .
The Core Idea: Pre-computation
A prefix sum (or cumulative sum) at an index i is the sum of all elements from the beginning of the array up to and including index i. We can build a new array, let's call it prefix_sums, to store these values.
Let's say our original array is nums. The prefix_sums array would be constructed as follows:
prefix_sums[0] = nums[0]prefix_sums[1] = nums[0] + nums[1]prefix_sums[2] = nums[0] + nums[1] + nums[2]- ...and so on.
More formally, prefix_sums[i] = prefix_sums[i-1] + nums[i].
Once we have this prefix_sums array, how can we find the sum of a range [i, j]? The sum of elements from i to j is the total sum up to j minus the total sum up to i-1.
This gives us a simple formula: sum(i, j) = prefix_sums[j] - prefix_sums[i-1].
There's a small edge case to handle: what if the range starts at index 0 (i=0)? prefix_sums[i-1] would be out of bounds. A common and elegant way to handle this is to pad the prefix sum array with an initial zero. If prefix_sums has size N+1 and prefix_sums[0] = 0, then prefix_sums[i+1] stores the sum of nums[0...i]. The formula then becomes sum(i, j) = prefix_sums[j+1] - prefix_sums[i], which works for all valid i and j.
To see this in action, let's look at a classic LeetCode problem.
Guide to Prefix Sum/Cumulative Sum Technique in Python
This Medium article provides an excellent, step-by-step walkthrough of the prefix sum technique using "LeetCode 303: Range Sum Query — Immutable" as its primary example. It will formalize the concepts we've just discussed.
Read the introduction, which frames the problem: The need for efficiency. Understand the problem statement and constraints in the section "What's the problem asking?". Notice the high number of potential calls to sumRange, which signals that a naive solution will be too slow. Study the core logic and the Python implementation under "How to Solve This Efficiently?". This implementation uses the padding trick with an initial zero. Contrast this with the naive approach to understand why it would fail under the given constraints. Read the "Back to the Code Example" and "Why is this O(1)?" sections for a detailed breakdown of the time complexity and the trade-off involved.
The video below also provides a great visual explanation of this same problem and solution.
Range Sum Query Immutable - Leetcode 303 - Python
This NeetCodeIO video covers the same LeetCode problem, providing a clear visual and code walkthrough.
Watch the introduction to see why the simple O(n) per query approach is suboptimal: the problem and naive solution. Pay close attention to the explanation of how prefix sums are computed and stored. The core logic of using subtraction to find the range sum is explained between these timestamps. Finally, review the concise Python implementation, which demonstrates the NumArray class structure common in such problems.
Advanced Application: Subarray Sum Equals K
The prefix sum technique is not just for simple range sum queries. It can be a key component in solving more complex problems. A classic example is "LeetCode 560: Subarray Sum Equals K," which asks you to find the total number of contiguous subarrays whose sum equals a target k.
A sliding window approach fails here because the array can contain negative numbers. Expanding the window doesn't guarantee the sum increases, and shrinking it doesn't guarantee the sum decreases, violating the core assumption of the sliding window pattern.
So, how can we use prefix sums?
Let the cumulative sum up to index i be prefix_sum[i]. We are at index j and have a current_sum = prefix_sum[j]. We are looking for a subarray ending at j that sums to k. This means we are looking for a starting index i <= j such that sum(nums[i...j]) = k.
Using our prefix sum knowledge, we know that sum(nums[i...j]) = prefix_sum[j] - prefix_sum[i-1].
So, we are looking for an index i-1 where:k = prefix_sum[j] - prefix_sum[i-1]
Rearranging this gives:prefix_sum[i-1] = prefix_sum[j] - k
This insight is the key! As we iterate through the array and calculate the current_sum (which is prefix_sum[j]), we don't need to look back at all possible subarrays. We just need to ask: "How many times have we previously seen a prefix sum equal to current_sum - k?"
A hash map is the perfect tool for this. We can store the frequencies of the prefix sums we've encountered so far. For each element, we update the current_sum, check the hash map for current_sum - k, add the count to our result, and then update the hash map with the current_sum.
Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python
This NeetCode video explains the solution to "Subarray Sum Equals K" brilliantly. It's a must-watch for understanding this common and powerful pattern.
First, understand why simpler patterns don't work. The video explains why sliding window fails due to negative numbers. The core logic is developed between these timestamps. Focus on the equation sum - k and how it relates to finding a previous prefix. Follow the detailed walkthrough of the algorithm with an example array. Pay special attention to the base case of adding a prefix sum of 0 with a count of 1 to the hash map. This handles subarrays that start from the beginning of the array. Finally, review the Python code, which is surprisingly concise once the logic is understood.
This combination of prefix sums and hash maps is an extremely common pattern for "subarray sum" type problems in interviews.
Extension to 2D: Prefix Sum Matrix
The prefix sum concept extends naturally to two dimensions. For a 2D matrix, we can pre-compute a prefix_sum_matrix where M[i][j] stores the sum of all elements in the rectangle from (0, 0) to (i, j).
This requires using the inclusion-exclusion principle. The sum of the rectangle ending at (i, j) is the sum of the rectangle above it, plus the sum of the rectangle to its left, minus the overlapping rectangle at the top-left (which was double-counted), plus the value of the current cell arr[i][j].
Once this 2D prefix matrix is built, you can find the sum of any submatrix—defined by its top-left corner (r1, c1) and bottom-right corner (r2, c2)—in O(1) time, again using the inclusion-exclusion principle.
Prefix Sum of Matrix (Or 2D Array)
This GeeksforGeeks article provides a clear guide to 2D prefix sums.
First, read the introduction to understand what a prefix sum matrix is. Study the formula and the Python code for its construction in the section "How to Construct". The visual diagram is very helpful here. Next, learn how to use this matrix to find the sum of an arbitrary submatrix in the section "How to Query". Finally, review the complexity analysis. The preprocessing takes O(N \cdot M) time, but each query is O(1).
Conclusion
You have now added another fundamental array pattern to your problem-solving arsenal. The prefix sum technique is a prime example of how a clever pre-computation step can dramatically improve the efficiency of an algorithm that involves repeated queries.
Key Takeaways:
- Prefix Sum: A technique that involves pre-calculating the cumulative sum at each position in an array.
- 1D Range Queries: It reduces the time for each range sum query from to after an initial setup cost. The core formula is
sum(i, j) = prefix[j+1] - prefix[i](using a 0-padded prefix array). - Advanced Applications: When combined with a hash map, it can efficiently solve complex problems like "Subarray Sum Equals K" by checking for
current_sum - k. - 2D Extension: The pattern generalizes to 2D matrices using the inclusion-exclusion principle for both building the prefix matrix and for querying submatrix sums.
In our "Subarray Sum Equals K" example, we saw a preview of the power of hash maps. In the next lesson, we will dive deep into hash maps, exploring the various patterns and problems they can solve, from frequency counting to grouping and aggregation.