LeetCode 303: Range Sum Query - Immutable - Comprehensive Solutions Guide

Problem Statement

Design a class that can efficiently calculate the sum of elements in a given range of an immutable integer array.

Constraints

- You must implement the `NumArray` class:

NumArray(int[] nums) Initializes the object with the integer array nums
int sumRange(int left, int right) Returns the sum of elements between indices left and right inclusive
1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
0 <= left <= right < nums.length
At most 10^4 calls will be made to sumRange

Example

Example in Python

Input:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output:
[null, 1, -1, -3]

Explanation:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

## Understanding the Problem We need to design a class that: 1. Preprocesses an immutable array 2. Efficiently answers multiple range sum queries 3. Optimizes for the case where sumRange is called many times Key insight: Precompute prefix sums to answer range queries in O(1) time per query. ## Solution 1: Prefix Sum Array (Optimal Solution)

Explanation

This approach uses a prefix sum array: 1. Initialization: Compute cumulative sums where prefix[i] is the sum of nums[0..i-1] 2. Query: The sum from index left to right is prefix[right+1] - prefix[left]

Step-by-Step Example

For nums = [-2, 0, 3, -5, 2, -1]: 1. prefix = [0, -2, -2, 1, -4, -2, -3] 2. sumRange(0, 2): prefix[3] - prefix[0] = 1 - 0 = 1 3. sumRange(2, 5): prefix[6] - prefix[2] = -3 - (-2) = -1

Python Implementation

Example in Python

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]

Complexity Analysis

Initialization Time: O(n) - one pass through array
Query Time: O(1) - constant time per query
Space Complexity: O(n) - for storing prefix sums
Why Optimal: Perfect for frequent range queries on immutable arrays

Solution 2: Caching All Possible Ranges (Alternative)

Explanation

This alternative precomputes all possible range sums: 1. Initialization: Compute and store sums for all possible ranges 2. Query: Direct lookup of precomputed results

Python Implementation

Example in Python

class NumArray:
    def __init__(self, nums: list[int]):
        n = len(nums)
        self.dp = [[0]*n for _ in range(n)]
        for i in range(n):
            total = 0
            for j in range(i, n):
                total += nums[j]
                self.dp[i][j] = total

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

Complexity Analysis

Initialization Time: O(n²) - computes all possible ranges
Query Time: O(1) - direct lookup
Space Complexity: O(n²) - stores all range sums
Pros: Fastest possible queries
Cons: Impractical for large n due to O(n²) space

Edge Cases to Consider

Single element array: Should return the element itself
Full range query: Should return sum of entire array
Same left and right: Should return single element
Negative numbers: Should handle negative sums correctly
Large input size: Must handle max constraints efficiently

Performance Comparison

Approach	Initialization Time	Query Time	Space Complexity	Best Use Case
Prefix Sum	O(n)	O(1)	O(n)	General case
Cached Ranges	O(n²)	O(1)	O(n²)	Small arrays

Final Recommendations

Prefix sum solution is the clear winner for most cases
Cached ranges demonstrate an alternative extreme (fast queries but huge space)
The problem teaches important preprocessing techniques
Understanding prefix sums is fundamental for many range query problems