Range Sum Query - Immutable
EasyPrompt
Given an integer array nums, handle multiple queries of the following type:
- Calculate the sum of the elements of
numsbetween indicesleftandrightinclusive whereleft <= right.
Implement the NumArray class:
NumArray(int[] nums)Initializes the object with the integer arraynums.int sumRange(int left, int right)Returns the sum of the elements ofnumsbetween indicesleftandrightinclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 1050 <= left <= right < nums.length- At most
104calls will be made tosumRange.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to calculate the sum for each query by iterating through the range from left to right index. This approach doesn't require any preprocessing but has poor performance for multiple queries.
Algorithm
- Store the original array in the constructor
- For each
sumRange(left, right)query:- Initialize sum to 0
- Iterate from index
lefttoright - Add each element to the sum
- Return the accumulated sum
Walkthrough
For each sumRange(left, right) query, we iterate through the array from index left to right and accumulate the sum. This is the most naive approach where we don't store any additional information and compute the sum fresh for every query.
class NumArray { private int[] nums; public NumArray(int[] nums) { this.nums = nums; } public int sumRange(int left, int right) { int sum = 0; for (int i = left; i <= right; i++) { sum += nums[i]; } return sum; }}This approach is simple to implement but becomes inefficient when we have many queries, especially for large ranges.
Complexity
Time
O(n) per query, where n is the length of the range (right - left + 1). Constructor: O(1)
Space
O(1) additional space (only storing reference to original array)
Trade-offs
Pros
Simple to understand and implement
No additional space required beyond storing the original array
No preprocessing time needed
Cons
Inefficient for multiple queries
Time complexity grows linearly with range size
Redundant calculations for overlapping ranges
The optimal approach uses a prefix sum array to precompute cumulative sums. This allows us to answer any range sum query in constant time using the formula: sum(left, right) = prefixSum[right+1] - prefixSum[left].
Algorithm
- In constructor:
- Create a prefix sum array of size n+1
- Set prefixSum[0] = 0
- For each index i from 0 to n-1:
- prefixSum[i+1] = prefixSum[i] + nums[i]
- For each
sumRange(left, right)query:- Return prefixSum[right+1] - prefixSum[left]
Walkthrough
We precompute a prefix sum array where prefixSum[i] represents the sum of elements from index 0 to i-1. This preprocessing allows us to answer any range query in O(1) time using the mathematical property that the sum of elements from index left to right equals prefixSum[right+1] - prefixSum[left].
class NumArray { private int[] prefixSum; public NumArray(int[] nums) { prefixSum = new int[nums.length + 1]; // prefixSum[0] = 0 (sum of no elements) for (int i = 0; i < nums.length; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } } public int sumRange(int left, int right) { return prefixSum[right + 1] - prefixSum[left]; }}The key insight is that if we know the cumulative sum up to any index, we can find the sum of any subarray by subtracting the cumulative sum before the start of our range from the cumulative sum at the end of our range.
Complexity
Time
O(n) for constructor preprocessing, O(1) per query where n is the length of the input array
Space
O(n) for storing the prefix sum array
Trade-offs
Pros
Constant time query after preprocessing
Optimal for multiple queries
Simple mathematical formula for range sum
Handles edge cases naturally
Cons
Requires additional space for prefix sum array
Preprocessing time needed during construction
Not suitable if the original array changes frequently
Solutions
Solution
class NumArray { private int [] s ; public NumArray ( int [] nums ) { int n = nums . length ; s = new int [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } } public int sumRange ( int left , int right ) { return s [ right + 1 ] - s [ left ]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); *//** * @param {number[]} nums */ var NumArray = function (nums) { const n = nums.length; this.s = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { this.s[i + 1] = this.s[i] + nums[i]; }};/** * @param {number} left * @param {number} right * @return {number} */ NumArray.prototype.sumRange = function (left, right) { return this.s[right + 1] - this.s[left]; }; /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(left,right) */class NumArray { public: NumArray ( vector < int >& nums ) { int n = nums . size (); s . resize ( n + 1 ); for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } } int sumRange ( int left , int right ) { return s [ right + 1 ] - s [ left ]; } private: vector < int > s ; }; /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj->sumRange(left,right); */''' >>> from itertools import accumulate >>> accumulate([1,2,3]) <itertools.accumulate object at 0x108f38340> >>> list(accumulate([1,2,3])) [1, 3, 6] >>> list(accumulate([1,2,3], initial=0)) [0, 1, 3, 6] >>> list(accumulate([1,2,3], initial=10)) [10, 11, 13, 16] ''' # note: when using python2, I always got error when importing it, via itertools.accumulate() # switching to python3, then all good for itertools.accumulate() class NumArray : def __init__ ( self , nums : List [ int ]): self . s = list ( accumulate ( nums , initial = 0 )) def sumRange ( self , left : int , right : int ) -> int : return self . s [ right + 1 ] - self . s [ left ] # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # param_1 = obj.sumRange(left,right) ############ class NumArray ( object ): def __init__ ( self , nums ): """ initialize your data structure here. :type nums: List[int] """ self . dp = [ 0 ] * ( len ( nums ) + 1 ) for i in range ( 0 , len ( nums )): self . dp [ i + 1 ] = self . dp [ i ] + nums [ i ] def sumRange ( self , i , j ): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ return self . dp [ j + 1 ] - self . dp [ i ] # Your NumArray object will be instantiated and called as such: # numArray = NumArray(nums) # numArray.sumRange(0, 1) # numArray.sumRange(1, 2)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.