Range Sum Query Immutable
- 2 min read
- Nums
- Nums
- Nums
- Nums
- Array
- LC-Easy
- Prefixes
- Prefixes
- Prefixes
- Prefixes
3 years ago
Solution
- Also look at Subarray Sum Equals K
- Naive solution is calculate sum each time
- Better solution is to pre-compute all possible values and store. But this would lead to O(n^2) memory
- Best solution is to calculate prefix sum for all indices
- The sum of a subarray is the prefix sum up until that point MINUS the prefix sum of all the numbers that came before it.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) | |
def __init__(self, nums: List[int]):
prefix = []
prefix_sum = 0
for num in nums:
prefix.append(prefix_sum + num)
prefix_sum += num
self.prefix = prefix
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right] - (self.prefix[left - 1] if left - 1 >= 0 else 0)
VV clean solution
Using the actual array instead of initializing a new one
Also using the array itself to get the last prefix value instead of having a separate variable
def __init__(self, nums: List[int]):
self.prefix_sums = [0]
for num in nums:
self.prefix_sums.append(self.prefix_sums[-1] + num)
def sumRange(self, left: int, right: int) -> int:
return self.prefix_sums[right + 1] - self.prefix_sums[left]
JavaScript Solution
Slightly inefficient since we're using extra space to store the numbers + an extra array access (to subtract this.[left])
class NumArray {
: number[] = [];
: number[] = [];
calculatePrefixes(nums: number[]) {
this.= nums;
let prefix = 0;
for(let i = 0; i < nums.length; i++) {
prefix += nums[i];
this.[i] = prefix;
}
}
constructor(nums: number[]) {
this.calculatePrefixes(nums);
}
sumRange(left: number, right: number): number {
return this.[right] - this.[left] + this.[left];
}
}