Difficulty: Easy | Acceptance: 72.10% | Paid: No Topics: Array, Design, Prefix Sum
Given an integer array nums, handle multiple queries of the following type:
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:
NumArray(int[] nums) Initializes the object with the integer array nums. int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + … + nums[right]).
- Examples
- Constraints
- Approach 1: Brute Force
- Approach 2: Prefix Sum
Examples
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 <= 10^4
- -10^5 <= nums[i] <= 10^5
- 0 <= left <= right < nums.length
- At most 10^4 calls will be made to sumRange.
Brute Force
Intuition For each query, iterate through the array from index left to right and sum all elements.
Steps
- Store the original array in the constructor.
- For sumRange, iterate from left to right and accumulate the sum.
class NumArray:
def __init__(self, nums):
self.nums = nums
def sumRange(self, left, right):
total = 0
for i in range(left, right + 1):
total += self.nums[i]
return total
Complexity
- Time: O(n) per query, where n is the length of the range
- Space: O(1) additional space
- Notes: Simple but inefficient for multiple queries
Prefix Sum
Intuition Precompute cumulative sums where prefix[i] stores the sum of elements from index 0 to i-1. Then sumRange(left, right) = prefix[right+1] - prefix[left].
Steps
- Build a prefix sum array where prefix[0] = 0 and prefix[i] = prefix[i-1] + nums[i-1].
- For sumRange, return prefix[right+1] - prefix[left].
class NumArray:
def __init__(self, nums):
self.prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]
Complexity
- Time: O(1) per query, O(n) preprocessing
- Space: O(n) for the prefix array
- Notes: Optimal solution for multiple queries on immutable array