LeetCode Solutions Blog

Range Sum Query - Immutable

Number: 303

Difficulty: Easy

Paid? No

Problem Description

Given an integer array, answer multiple queries asking for the sum of elements between two indices (inclusive).

Key Insights

Precompute a prefix sum array during initialization.
The sum for any given range can be computed in O(1) by subtracting the prefix sum at the starting index from the prefix sum at the ending index + 1.
This approach makes use of extra O(n) space but provides fast queries.

Space and Time Complexity

Time Complexity: O(n) for preprocessing and O(1) per query.
Space Complexity: O(n) for storing the prefix sum array.

Solution

We build a prefix sum array such that each element at index i+1 represents the sum of the first i elements. For any query (left, right), the sum of elements between left and right is given by prefix[right+1] - prefix[left]. This approach leverages preprocessing to optimize query performance.

Code Solutions

class NumArray:
    def __init__(self, nums: list[int]):
        # Create prefix sum array with an extra 0 at the beginning.
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            # Each element at prefix[i+1] is the sum of nums[0] to nums[i].
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        # Return sum of elements from index left to right inclusive.
        return self.prefix[right + 1] - self.prefix[left]

# Example Usage:
# numArray = NumArray([-2, 0, 3, -5, 2, -1])
# print(numArray.sumRange(0, 2))  # Output: 1
# print(numArray.sumRange(2, 5))  # Output: -1
# print(numArray.sumRange(0, 5))  # Output: -3