303. Range Sum Query - Immutable
Model: qwen2.5-coder:14b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 48.2%
Problem Breakdown
The problem requires implementing a class NumArray that can efficiently compute the sum of elements in a given range [left, right] of an integer array nums. The key inputs are:
- An integer array
numsduring initialization. - Two integers
leftandrightfor each query.
The output is the sum of the elements from index left to right, inclusive. The constraints include:
- The length of
numscan be up to 10,000. - Each element in
numscan range from -100,000 to 100,000. - There can be up to 10,000 calls to
sumRange.
Implicit constraints and edge cases include:
- Handling empty input arrays.
- Negative numbers within the array.
- Multiple queries that may overlap or cover the entire array.
Intuition
A brute-force approach would involve iterating through the subarray from left to right for each query, resulting in a time complexity of O(n) per query. Given that there can be up to 10,000 calls to sumRange, this approach is inefficient and would likely exceed time limits.
The key insight is to preprocess the array during initialization to allow constant-time range sum queries. This can be achieved using prefix sums (also known as cumulative sums). By storing the cumulative sum of elements up to each index, we can compute any range sum in O(1) time by subtracting the appropriate prefix sums.
Approach
-
Initialization (
__init__method):- Create a prefix sum array
prefix_sumswhereprefix_sums[i]stores the sum of elements from the start of the array up to indexi. - Iterate through the input array
numsand compute the cumulative sums, storing them inprefix_sums.
- Create a prefix sum array
-
Range Sum Query (
sumRangemethod):- To get the sum of elements between indices
leftandright, use the formula: [ \text{sumRange}(left, right) = prefix_sums[right + 1] - prefix_sums[left] ] - If
leftis 0, simply returnprefix_sums[right + 1].
- To get the sum of elements between indices
This approach leverages the precomputed prefix sums to answer each query in constant time.
Complexity Analysis
- Time Complexity:
- Initialization (
__init__method): O(n), where n is the length of the input arraynums. - Range Sum Query (
sumRangemethod): O(1) for each query.
- Initialization (
- Space Complexity:
- O(n) due to the additional storage required for the prefix sums array.
Solution
class NumArray:
def __init__(self, nums: List[int]):
# Initialize the prefix sums array with an extra space for easier calculation
self.prefix_sums = [0] * (len(nums) + 1)
# Compute the prefix sums
for i in range(len(nums)):
self.prefix_sums[i + 1] = self.prefix_sums[i] + nums[i]
def sumRange(self, left: int, right: int) -> int:
# Return the sum of elements between indices left and right inclusive
return self.prefix_sums[right + 1] - self.prefix_sums[left]
Edge Cases Handled
- Empty Array: If
numsis empty, the prefix sums array will also be empty. Any query on an empty array will correctly return 0. - Single Element Array: The prefix sum for a single-element array will simply be that element itself. Queries on such arrays will handle this naturally.
- Negative Numbers: The algorithm handles negative numbers correctly by using cumulative sums, which can result in both positive and negative values.
- Multiple Overlapping Queries: The constant-time query allows handling multiple overlapping or sequential queries efficiently without recalculating sums repeatedly.