Prefix Sums for O(1) Range Queries

1. The Problem: Handling Multiple Range Sum Queries

Imagine you are given an array of numbers and are asked to calculate the sum of elements between various pairs of indices [left, right]. This is known as a range sum query.

A simple approach would be to loop from left to right and add up the numbers for each query.

• For a single query: The time complexity is O(right - left), which in the worst case is O(n).
• For Q queries: The total time complexity becomes O(n * Q).

In a typical interview setting, n and Q can be up to 10,000 or more, making an O(n * Q) solution too slow. This is where we need a more intelligent approach.

2. The Solution: Pre-computation with Prefix Sums

The key to optimizing this problem is to perform a one-time pre-computation. We can create an auxiliary array, often called prefix_sum, that stores the cumulative sum of the original array at each index.

A prefix sum at index i is the sum of all elements from the beginning of the array up to and including index i.

prefix_sum[i] = nums[0] + nums[1] + ... + nums[i]

We can build this array in a single pass, with each new prefix sum being the previous prefix sum plus the current number:

This pre-computation step takes O(n) time and requires O(n) extra space.

Let's visualize how this array is built.

A Small but Important Trick: Padding with a Zero

In practice, it's highly convenient to make the prefix sum array one element longer than the input array and initialize the first element to 0. This simplifies the formula for querying and elegantly handles edge cases where the range starts at index 0.

If nums = [-2, 0, 3], our padded prefix sum array would be [0, -2, -2, 1].

• prefix[0] = 0
• prefix[1] = prefix[0] + nums[0] = 0 + (-2) = -2
• prefix[2] = prefix[1] + nums[1] = -2 + 0 = -2
• prefix[3] = prefix[2] + nums[2] = -2 + 3 = 1

With this structure, prefix[i] now stores the sum of the first i elements of nums.

3. Answering Queries in O(1) Time

Once we have our pre-computed prefix sum array, how do we find the sum of elements between indices left and right (inclusive)?

The sum of elements from index left to right is the total sum up to right minus the total sum up to left - 1.

Using our padded prefix sum array, the formula is beautifully simple:

• prefix_sum[right + 1] gives the cumulative sum up to and including nums[right].
• prefix_sum[left] gives the cumulative sum of all elements before nums[left].

Subtracting the two leaves us with exactly the sum of nums[left] through nums[right]. Since this involves just two array lookups and one subtraction, each query takes O(1) time.

Now, let's see this logic applied in a video walkthrough, which also covers the edge case for when the range starts at index 0.

4. Implementation Template

Here is a template for the NumArray class, which is how this problem (LeetCode 303) is often presented in interviews. Your background in OOP should make this class-based structure very familiar.

class NumArray:
    def __init__(self, nums: list[int]):
        # Initialize a prefix sum array with a leading zero.
        self.prefix_sum = [0] * (len(nums) + 1)
        
        # Pre-compute the prefix sums in O(n) time.
        for i in range(len(nums)):
            self.prefix_sum[i+1] = self.prefix_sum[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        # Calculate the sum in O(1) time using the pre-computed array.
        # Note: self.prefix_sum is 1-indexed relative to the original array.
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

# Example Usage:
# nums = [-2, 0, 3, -5, 2, -1]
# numArray = NumArray(nums)
# print(numArray.sumRange(0, 2))  # Output: 1
# print(numArray.sumRange(2, 5))  # Output: -1

5. Advanced Application: Combining with Hash Maps

The prefix sum pattern becomes even more powerful when combined with other data structures. A very common interview problem is "Subarray Sum Equals K," which asks for the number of contiguous subarrays that sum to a target k.

The key insight is:
If sum(i, j) = k, then prefix[j] - prefix[i-1] = k.
Rearranging this gives: prefix[i-1] = prefix[j] - k.

This means that as we iterate through the array and calculate the current prefix sum prefix[j], we can ask: "How many times have we previously seen a prefix sum equal to prefix[j] - k?" We can answer this question efficiently by storing the counts of all previously seen prefix sums in a hash map.

This is a fantastic example of combining two patterns and serves as a great bridge to our next module on hashing.

Conclusion

Congratulations on completing the module on high-ROI interview patterns! You've now added prefix sums to your arsenal, a crucial technique for efficiently handling range-based queries on arrays.

Key Takeaways:

• Core Idea: Prefix sums involve a one-time pre-computation (O(n) time, O(n) space) to create a cumulative sum array.
• O(1) Queries: This pre-computation allows any subsequent range sum query to be answered in constant time (O(1)).
• The Formula: The sum of nums[left...right] is prefix_sum[right+1] - prefix_sum[left] when using a 0-padded prefix sum array.
• Time-Space Tradeoff: This pattern is a classic example of using extra space to achieve a significant speedup in time complexity, a concept highly valued in system design and algorithm interviews.
• Beyond Sums: The concept can be extended to products, XORs, and combined with other data structures like hash maps to solve a wider variety of problems.

In our next lesson, we will begin a new module, "Hashing for Efficient Lookups." We'll dive deep into how hash maps and hash sets work, and how they provide O(1) average time complexity for lookups, insertions, and deletions, making them one of the most versatile tools in a programmer's toolkit.