Range Sum Query Immutable LeetCode 303

LeetCode 303 — Range Sum Query Immutable asks you to implement a NumArray class that accepts an integer array nums in its constructor and exposes a sumRange(left, right) method that returns the sum of elements from index left to index right inclusive. The array never changes after initialization, which is the key insight enabling precomputation.

The challenge is that sumRange will be called many times — potentially thousands of times on the same array. A naive solution that loops from left to right on every call costs O(n) per query, which becomes O(n * q) total where q is the number of queries. For large inputs this is unacceptably slow.

Because the array is immutable, you are free to do arbitrary preprocessing in the constructor. This transforms the problem into a classic trade-off: spend O(n) time and O(n) space once up front, then answer every query in O(1). The prefix sum pattern is the canonical solution to this family of problems.

The naive approach implements sumRange by looping from index left to right and accumulating the sum: return sum(nums[left:right+1]) in Python. This is simple and correct but costs O(n) per call. If sumRange is called q times, the total cost is O(n * q) — for n=10000 and q=10000, that is 100 million operations.

The prefix sum approach precomputes a cumulative sum array in the constructor so each sumRange call is a single subtraction. During initialization, build an array prefix of length n+1 where prefix[i] stores the sum of the first i elements of nums. Then sumRange(left, right) = prefix[right+1] - prefix[left], computed in O(1) regardless of the range size.

The trade-off is clear: prefix sum spends O(n) time and O(n) extra space in the constructor, then answers every query in O(1). For any problem where sumRange is called more than once this is a net win, and the problem statement explicitly states sumRange is called many times — making prefix sums the intended solution.

The prefix array has length n+1 where n is the length of nums. This 1-indexed design is deliberate: prefix[0] is always 0, and prefix[i] = prefix[i-1] + nums[i-1] for i from 1 to n. In other words, prefix[i] stores the sum of nums[0] through nums[i-1] inclusive — the sum of the first i elements.

The recurrence prefix[i+1] = prefix[i] + nums[i] lets you build the entire array in a single left-to-right pass. Starting from prefix[0] = 0, each entry is the previous entry plus the corresponding element of nums. The result is a cumulative sum array that encodes every possible prefix sum of the input.

The n+1 length with prefix[0]=0 is the key design decision. It means you never need a special case for the boundary where left equals 0: prefix[right+1] - prefix[0] = prefix[right+1] - 0 = prefix[right+1], which is exactly the sum from the beginning of the array to index right. Without this sentinel zero, you would need an if-statement for left==0.

Once the prefix array is built, sumRange(left, right) is a one-liner: return prefix[right+1] - prefix[left]. This works because prefix[right+1] is the sum of nums[0..right] and prefix[left] is the sum of nums[0..left-1]. Subtracting cancels the shared prefix, leaving the sum of nums[left..right].

The formula is a direct application of the inclusion-exclusion principle for prefix sums. Any subarray sum can be expressed as the difference of two prefix sums: sum(left, right) = total_sum_to_right - total_sum_before_left. The 1-indexed prefix array makes both of these lookups straightforward array accesses with no boundary arithmetic.

Every sumRange call now does exactly two array lookups and one subtraction — O(1) regardless of how large right-left is. Whether the query spans a single element or the entire array, the cost is identical. This constant-time guarantee is what makes the NumArray class scalable for large numbers of queries.

Consider nums = [-2, 0, 3, -5, 2, -1]. The prefix array of length 7 is built as: prefix[0]=0, prefix[1]=0+(-2)=-2, prefix[2]=-2+0=-2, prefix[3]=-2+3=1, prefix[4]=1+(-5)=-4, prefix[5]=-4+2=-2, prefix[6]=-2+(-1)=-3. So prefix = [0, -2, -2, 1, -4, -2, -3].

Now run sumRange(0, 2): prefix[3] - prefix[0] = 1 - 0 = 1. Manual check: -2 + 0 + 3 = 1. Correct. Run sumRange(2, 5): prefix[6] - prefix[2] = -3 - (-2) = -1. Manual check: 3 + (-5) + 2 + (-1) = -1. Correct. Run sumRange(0, 5): prefix[6] - prefix[0] = -3 - 0 = -3. Manual check: sum of all = -2+0+3-5+2-1 = -3. Correct.

Notice that sumRange(0, 5) uses prefix[0]=0, which confirms the sentinel eliminates special-casing for left==0. In all three queries the formula prefix[right+1] - prefix[left] works without modification, and each query costs exactly one subtraction after the two array lookups.

Python: class NumArray: def __init__(self, nums): n=len(nums); self.prefix=[0]*(n+1); for i in range(n): self.prefix[i+1]=self.prefix[i]+nums[i]; def sumRange(self, left, right): return self.prefix[right+1]-self.prefix[left]. Constructor is O(n), sumRange is O(1). The prefix list is the only extra data structure needed.

Java: class NumArray { private int[] prefix; public NumArray(int[] nums) { int n=nums.length; prefix=new int[n+1]; for(int i=0;i<n;i++) prefix[i+1]=prefix[i]+nums[i]; } public int sumRange(int left, int right) { return prefix[right+1]-prefix[left]; } }. Identical logic — int[] is zero-initialized in Java so prefix[0]=0 is automatic. O(n) space, O(n) constructor, O(1) sumRange.

Both implementations follow the same structure: allocate a length-(n+1) array, fill it with cumulative sums starting from index 1, and implement sumRange as a single subtraction. The constructor and sumRange are both minimal — the entire solution fits in about five lines of logic. This conciseness is a hallmark of prefix sum problems: the preprocessing does all the work.

LeetCode 303 is the foundational prefix sum problem. The same precomputation pattern appears in Subarray Sum Equals K (LeetCode 560), which combines prefix sums with a hash map to count subarrays summing to a target in O(n). Product of Array Except Self (LeetCode 238) applies a similar left-and-right precomputation idea to products instead of sums.

Range Sum Query 2D Immutable (LeetCode 304) extends the 1D prefix sum to a 2D matrix, where the prefix table enables O(1) rectangular region sum queries after O(m*n) preprocessing. Maximum Subarray (LeetCode 53) can be solved with prefix sums by tracking the minimum prefix seen so far. These problems all share the core insight: precompute cumulative values to answer future queries cheaply.

The prefix sum pattern is one of the highest-leverage patterns in competitive programming and technical interviews. Recognizing when a problem involves repeated range queries over a static structure — arrays, matrices, trees — is the first step. Once identified, the prefix sum construction is mechanical, and the query formula follows directly from the inclusion-exclusion principle.