LeetCode 303: Range Sum Query - Immutable

Problem Restatement

We are given an integer array nums.

We need to implement a class called NumArray that supports range sum queries.

The class has two operations:

The query range is inclusive, so both left and right are included.

The array does not change after initialization. That is why the problem says immutable. The official problem asks for many range sum queries on the same array.

Input and Output

Class shape:

class NumArray:

    def __init__(self, nums: list[int]):
        ...

    def sumRange(self, left: int, right: int) -> int:
        ...

Examples

Example:

nums = [-2, 0, 3, -5, 2, -1]
numArray = NumArray(nums)

Query 1:

numArray.sumRange(0, 2)

This asks for:

nums[0] + nums[1] + nums[2]

So:

-2 + 0 + 3 = 1

Output:

1

Query 2:

numArray.sumRange(2, 5)

This asks for:

3 + (-5) + 2 + (-1)

Output:

-1

Query 3:

numArray.sumRange(0, 5)

This asks for the whole array sum.

-2 + 0 + 3 + (-5) + 2 + (-1) = -3

Output:

-3

First Thought: Sum Each Query Directly

The simplest implementation stores the original array.

Then for every query, loop from left to right and add the numbers.

class NumArray:

    def __init__(self, nums: list[int]):
        self.nums = nums

    def sumRange(self, left: int, right: int) -> int:
        total = 0

        for i in range(left, right + 1):
            total += self.nums[i]

        return total

This is correct.

But each query may scan many elements.

If the array length is n, one query can cost O(n) time. Since the problem allows many calls to sumRange, this can become slow.

Key Insight

The array never changes.

So we can do extra work once in the constructor, then answer each query quickly.

Use prefix sums.

A prefix sum array stores the sum of elements before each position.

For example:

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

Build:

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

So the full prefix array is:

The important formula is:

sum(nums[left:right + 1]) = prefix[right + 1] - prefix[left]

prefix[right + 1] includes everything from index 0 through right.

prefix[left] includes everything before left.

Subtracting removes the part before left, leaving only the requested range.

Algorithm

During initialization:

1. Create prefix with one starting value, 0.
2. Keep a running sum.
3. For each number in nums, add it to the running sum.
4. Append the running sum to prefix.

During sumRange(left, right):

1. Read prefix[right + 1].
2. Read prefix[left].
3. Return their difference.

Correctness

Let prefix[i] be the sum of the first i elements of nums.

That means:

prefix[i] = nums[0] + nums[1] + ... + nums[i - 1]

For a query sumRange(left, right), we want:

nums[left] + nums[left + 1] + ... + nums[right]

prefix[right + 1] contains:

nums[0] + nums[1] + ... + nums[left - 1] + nums[left] + ... + nums[right]

prefix[left] contains:

nums[0] + nums[1] + ... + nums[left - 1]

When we subtract prefix[left] from prefix[right + 1], all elements before left cancel out.

The remaining value is exactly:

nums[left] + nums[left + 1] + ... + nums[right]

Therefore, sumRange returns the correct range sum.

Complexity

The stored prefix array has length n + 1.

Implementation

class NumArray:

    def __init__(self, nums: list[int]):
        self.prefix = [0]

        running = 0
        for num in nums:
            running += num
            self.prefix.append(running)

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

Code Explanation

The constructor starts with:

self.prefix = [0]

This extra leading zero makes the range formula clean.

Without it, queries starting at index 0 need special handling.

Then we build the prefix array:

running = 0
for num in nums:
    running += num
    self.prefix.append(running)

After processing each number, running stores the sum of all numbers seen so far.

For sumRange, we return:

self.prefix[right + 1] - self.prefix[left]

The right + 1 index is used because prefix[k] stores the sum of the first k elements, not the sum up to index k.

Testing

def run_tests():
    arr = NumArray([-2, 0, 3, -5, 2, -1])

    assert arr.sumRange(0, 2) == 1
    assert arr.sumRange(2, 5) == -1
    assert arr.sumRange(0, 5) == -3

    single = NumArray([7])
    assert single.sumRange(0, 0) == 7

    zeros = NumArray([0, 0, 0])
    assert zeros.sumRange(0, 2) == 0
    assert zeros.sumRange(1, 1) == 0

    mixed = NumArray([5, -3, 8, -2])
    assert mixed.sumRange(0, 0) == 5
    assert mixed.sumRange(1, 3) == 3
    assert mixed.sumRange(0, 3) == 8

    print("all tests passed")

run_tests()

Test meaning: