Range Sum Query - Immutable
Asked at Meta, Microsoft
Problem
Design a NumArray class that computes the sum of elements between indices left and right inclusive. Precompute a prefix sum array so each query is answered in O(1) time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
| Microsoft | Easy | View all Microsoft questions → |
How to Think About It
Brute force: for each query, loop from left to right and sum. That's O(n) per query. With q queries, total is O(n*q). Too slow for repeated queries.
Key insight: precompute a prefix sum array. prefix[i] = sum of all elements from index 0 to i-1. Then the sum from left to right is prefix[right+1] - prefix[left]. Each query becomes O(1).
Why it works: imagine the array [1, 2, 3, 4]. prefix = [0, 1, 3, 6, 10]. Sum from index 1 to 3 = prefix[4] - prefix[1] = 10 - 1 = 9. That matches 2+3+4 = 9.
Visual walkthrough for nums = [-2, 0, 3, -5, 2, -1]:
prefix[0] = 0
prefix[1] = -2
prefix[2] = -2 + 0 = -2
prefix[3] = -2 + 3 = 1
prefix[4] = 1 + (-5) = -4
prefix[5] = -4 + 2 = -2
prefix[6] = -2 + (-1) = -3
Query sum(2,5): prefix[6] - prefix[2] = -3 - (-2) = -1. Check: 3+(-5)+2+(-1) = -1.
Edge cases: query(0, n-1) returns prefix[n] (total sum). Query(i, i) returns a single element: prefix[i+1] - prefix[i]. Empty array is not possible by constraints.
Time complexity: build prefix array is O(n). Each query is O(1). Space: O(n) for the prefix array.
Optimal Approach
In __init__, build a prefix sum array of length n+1. Initialize prefix[0] = 0. For i from 0 to n-1, set prefix[i+1] = prefix[i] + nums[i].
In sumRange(left, right), return prefix[right+1] - prefix[left].
Walkthrough with nums = [-2, 0, 3, -5, 2, -1]:
- Build
prefix = [0, -2, -2, 1, -4, -2, -3] sumRange(0, 2)=prefix[3]-prefix[0]= 1 - 0 = 1. Check: -2+0+3 = 1.sumRange(2, 5)=prefix[6]-prefix[2]= -3 - (-2) = -1. Check: 3+(-5)+2+(-1) = -1.sumRange(0, 5)=prefix[6]-prefix[0]= -3 - 0 = -3. Total sum.
Time: O(n) to build, O(1) per query. Space: O(n) for prefix array.
What Trips People Up in Real Interviews
Off-by-one in the prefix array. prefix[i] stores the sum of elements 0 through i-1, not 0 through i. So the sum from left to right is prefix[right+1] - prefix[left], not prefix[right] - prefix[left-1].
Building the prefix array incorrectly. Start with prefix[0] = 0, then prefix[1] = nums[0], prefix[2] = nums[0]+nums[1], and so on. Don't try to store the cumulative sum at the same index as nums.
Forgetting that the prefix array has length n+1. You need one extra slot at the beginning. Using an array of length n and indexing with prefix[right] - prefix[left-1] works but is error-prone with left=0.
Confusing this with Range Sum Query 2D. The 2D variant uses a 2D prefix sum matrix. Don't mix up the formulas: 1D uses subtraction, 2D uses inclusion-exclusion.
Not handling the single-element case. sumRange(i, i) should return nums[i]. With the prefix array: prefix[i+1] - prefix[i] = nums[i]. This works automatically.
Solution Code
class NumArray:
def __init__(self, nums):
self.prefix = [0] * (len(nums) + 1)
for i, num in enumerate(nums):
self.prefix[i + 1] = self.prefix[i] + num
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]Frequently Asked Questions
What is the Range Sum Query - Immutable problem?
Design a `NumArray` class that computes the sum of elements between indices `left` and `right` inclusive. Precompute a prefix sum array so each query is answered in `O(1)` time.
How do you solve Range Sum Query - Immutable?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Range Sum Query - Immutable?
Range Sum Query - Immutable is asked at Meta, Microsoft. It is a easy difficulty problem.
What are common mistakes on Range Sum Query - Immutable?
- Off-by-one in the prefix array. `prefix[i]` stores the sum of elements 0 through i-1, not 0 through i. So the sum from `left` to `right` is `prefix[right+1]` - `prefix[left]`, not `prefix[right]` - `prefix[left-1]`.
- Building the prefix array incorrectly. Start with `prefix[0] = 0`, then `prefix[1] = nums[0]`, `prefix[2] = nums[0]+nums[1]`, and so on. Don't try to store the cumulative sum at the same index as `nums`.
- Forgetting that the prefix array has length n+1. You need one extra slot at the beginning. Using an array of length n and indexing with `prefix[right]` - `prefix[left-1]` works but is error-prone with left=0.
- Confusing this with Range Sum Query 2D. The 2D variant uses a 2D prefix sum matrix. Don't mix up the formulas: 1D uses subtraction, 2D uses inclusion-exclusion.
- Not handling the single-element case. `sumRange(i, i)` should return `nums[i]`. With the prefix array: `prefix[i+1]` - `prefix[i]` = `nums[i]`. This works automatically.