303. Range Sum Query - Immutable
Asked at Meta, Microsoft
Difficulty
Easy
Time
O(n) to build, O(1) per query
Space
O(n)
Pattern
Array
Companies
2
Problem
Design a class NumArray that stores an integer array and answers many range-sum questions about it.
The constructor NumArray(nums) receives the array once. Then sumRange(left, right) is called many times, and each call must return the sum of nums[left] + nums[left+1] + ... + nums[right] — both ends included. The array never changes after construction, so the same stored data must serve every query.
Because there can be up to 10^4 queries, adding up the range from scratch each time is too slow. Precompute a prefix sum array in the constructor: prefix[i] holds the sum of the first i elements, with prefix[0] = 0. Then any range sum is just prefix[right+1] - prefix[left], which is a single subtraction.
Answering one range sum
Constraints
- ●
1 <= nums.length <= 10^4 - ●
-10^5 <= nums[i] <= 10^5 - ●
0 <= left <= right < nums.length - ●
At most 10^4 calls will be made to sumRange
Examples
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]][null, 1, -1, -3]Asked At
2 companies| 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.
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.
Prefix sums make each query one subtraction
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
O(n) to build, O(1) per query timeclass 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 runs in O(n) to build, O(1) per query time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.