LeetCode 303 - Range Sum Query - Immutable

LeetCode Problem 303

Difficulty: 🟢 Easy
Topics: Array, Design, Prefix Sum

Solution

Problem Understanding

The problem asks us to design a data structure that supports efficient range sum queries on a fixed array. We are given an integer array nums, and after initialization, the array never changes. The goal is to answer multiple queries of the form:

What is the sum of all elements between index left and index right, inclusive?

The class must support two operations:

• Initialization with the input array
• Querying the sum of any contiguous subarray

For example, if the array is:

[-2, 0, 3, -5, 2, -1]

and we query sumRange(0, 2), we compute:

-2 + 0 + 3 = 1

The important detail is that the array is immutable. This means values never change after construction. Since there may be many range sum queries, repeatedly recomputing sums from scratch would waste time.

The constraints are relatively small:

• nums.length <= 10^4
• Up to 10^4 calls to sumRange

Even though these constraints are manageable, a naive solution could still perform up to:

10^4 queries × 10^4 elements = 10^8 operations

which is unnecessarily expensive for such a simple problem.

Several edge cases are important:

• Arrays containing negative numbers
• Queries covering the entire array
• Queries where left == right, meaning the result is a single element
• Arrays of length 1
• Repeated queries over overlapping ranges

The problem guarantees valid indices and guarantees that left <= right, so we do not need to handle invalid input.

Approaches

Brute Force Approach

The most direct solution is to compute the sum every time sumRange is called.

For each query, we iterate from index left to right and accumulate the total.

This approach is correct because it literally follows the definition of the problem. Every requested element is included exactly once in the computation.

However, the performance is inefficient when there are many queries. If each query scans up to n elements, then each operation costs O(n) time.

With up to 10^4 queries, repeated iteration becomes expensive.

Optimal Approach, Prefix Sum

The key observation is that the array never changes.

Since the values are immutable, we can preprocess information once during initialization and reuse it for every query.

We build a prefix sum array where:

prefix[i]

stores the sum of all elements before index i.

More specifically:

prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
...

Using this structure, the sum of any range [left, right] can be computed in constant time:

prefix[right + 1] - prefix[left]

Why does this work?

• prefix[right + 1] contains the sum from index 0 through right
• prefix[left] contains the sum from index 0 through left - 1
• Subtracting them removes everything before left

This transforms each query from O(n) time to O(1) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per query	O(1)	Recomputes the range sum every time
Optimal	O(1) per query after preprocessing	O(n)	Uses prefix sums for constant-time queries

Algorithm Walkthrough

1. During initialization, create a prefix sum array with length len(nums) + 1.

The extra element at the beginning simplifies calculations and avoids edge-case handling for ranges starting at index 0. 2. Set the first prefix value to 0.

This represents the sum of zero elements. 3. Iterate through the input array and build cumulative sums.

For each index i:

prefix[i + 1] = prefix[i] + nums[i]

This means each position stores the sum of all previous elements. 4. When sumRange(left, right) is called, compute:

prefix[right + 1] - prefix[left]

The subtraction removes all elements before left, leaving only the desired range sum. 5. Return the computed result immediately.

No iteration over the range is necessary during queries.

Why it works

The correctness comes from the definition of the prefix sum array.

prefix[i] always stores the sum of elements from index 0 through i - 1.

Therefore:

prefix[right + 1]

contains the sum of elements from 0 through right.

Similarly:

prefix[left]

contains the sum of elements before the target range.

Subtracting the two removes unwanted elements and leaves exactly the sum from left to right.

Mathematically:

$\sum_{i=left}^{right} nums[i] = prefix[right+1] - prefix[left]$

Python Solution

from typing import List

class NumArray:

    def __init__(self, nums: List[int]):
        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: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left, right)

The implementation begins by constructing a prefix sum array during initialization. The array has one extra slot at the beginning initialized to 0.

For each index in nums, we compute the cumulative sum up to that position. This preprocessing step costs O(n) time but only happens once.

The sumRange method then performs a simple subtraction using the prefix sums. Because the necessary information has already been precomputed, each query runs in constant time.

The formula:

prefix[right + 1] - prefix[left]

directly extracts the sum of the requested subarray.

Go Solution

type NumArray struct {
	prefix []int
}

func Constructor(nums []int) NumArray {
	prefix := make([]int, len(nums)+1)

	for i := 0; i < len(nums); i++ {
		prefix[i+1] = prefix[i] + nums[i]
	}

	return NumArray{
		prefix: prefix,
	}
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.prefix[right+1] - this.prefix[left]
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */

The Go implementation follows the same logic as the Python solution. A slice named prefix stores cumulative sums.

Go slices are dynamically sized references to arrays, making them ideal for this use case. The constructor allocates a slice of length len(nums) + 1.

Unlike some languages, Go integers are platform-dependent, but the constraints here are small enough that integer overflow is not a concern.

The SumRange method performs the same constant-time subtraction used in Python.

Worked Examples

Example 1

Input array:

[-2, 0, 3, -5, 2, -1]

Step 1: Build Prefix Sum Array

Index	nums[i]	prefix value
0	-2	0
1	0	-2
2	3	-2
3	-5	1
4	2	-4
5	-1	-2

Final prefix array:

[0, -2, -2, 1, -4, -2, -3]

Query 1: sumRange(0, 2)

We compute:

prefix[3] - prefix[0]
= 1 - 0
= 1

Expression	Value
prefix[3]	1
prefix[0]	0
Result	1

Query 2: sumRange(2, 5)

We compute:

prefix[6] - prefix[2]
= -3 - (-2)
= -1

Expression	Value
prefix[6]	-3
prefix[2]	-2
Result	-1

Query 3: sumRange(0, 5)

We compute:

prefix[6] - prefix[0]
= -3 - 0
= -3

Expression	Value
prefix[6]	-3
prefix[0]	0
Result	-3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) preprocessing, O(1) per query	Building prefix sums takes linear time, each query is constant time
Space	O(n)	The prefix array stores one cumulative sum per element

The preprocessing phase iterates through the array exactly once, so initialization costs O(n) time.

After preprocessing, each query only performs two array lookups and one subtraction, resulting in O(1) time complexity.

The additional space comes from storing the prefix sum array, which contains n + 1 integers.

Test Cases

from typing import List

class NumArray:

    def __init__(self, nums: List[int]):
        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: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

# Provided example
obj = NumArray([-2, 0, 3, -5, 2, -1])
assert obj.sumRange(0, 2) == 1      # basic range query
assert obj.sumRange(2, 5) == -1     # includes negative values
assert obj.sumRange(0, 5) == -3     # entire array

# Single element array
obj = NumArray([5])
assert obj.sumRange(0, 0) == 5      # smallest valid input

# All positive numbers
obj = NumArray([1, 2, 3, 4, 5])
assert obj.sumRange(1, 3) == 9      # middle subarray

# All negative numbers
obj = NumArray([-1, -2, -3, -4])
assert obj.sumRange(0, 3) == -10    # full negative range

# Query single index
obj = NumArray([10, 20, 30])
assert obj.sumRange(1, 1) == 20     # left == right

# Large repeated queries
obj = NumArray([1] * 10000)
assert obj.sumRange(0, 9999) == 10000   # maximum range size
assert obj.sumRange(500, 5000) == 4501  # large internal range

# Mixed positive and negative values
obj = NumArray([3, -1, 4, -2, 5])
assert obj.sumRange(1, 4) == 6      # mixed values

# Prefix boundary check
obj = NumArray([7, 8, 9])
assert obj.sumRange(0, 1) == 15     # range starting at zero

Test	Why
Example input	Validates correctness against official examples
Single element array	Tests minimum array size
All positive numbers	Verifies standard accumulation
All negative numbers	Ensures negative sums are handled correctly
Single index query	Tests left == right
Large repeated queries	Confirms scalability and performance
Mixed positive and negative	Tests cancellation effects
Range starting at zero	Validates prefix boundary handling

Edge Cases

One important edge case occurs when the query range contains only a single element. In this situation, left == right. A buggy implementation might accidentally exclude the endpoint or mishandle subtraction boundaries. The prefix sum formula works correctly because:

prefix[right + 1] - prefix[left]

isolates exactly one value.

Another important edge case is when the query starts at index 0. Without the extra leading 0 in the prefix sum array, special-case logic would be necessary. By storing an initial 0, the implementation naturally handles ranges beginning at the start of the array.

Arrays containing negative values are also significant. Some incorrect approaches assume cumulative sums always increase, which is not true here. Prefix sums still work perfectly because the method depends only on arithmetic subtraction, not on monotonic behavior.

Finally, arrays of length 1 test whether initialization and indexing are implemented safely. Since the prefix array always has length n + 1, even the smallest valid input works correctly without out-of-bounds access.