Domain 1EasyCORE

Range Sum Query - Immutable

The problem requires implementing a class `NumArray` that can efficiently compute the sum of elements in a given range `[left, right]` of an integer array `nums`. The key inputs are: - An integer array `nums` during initialization. - Two integers `left` and `right` for each query.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Dynamic Programming

303. Range Sum Query - Immutable

Model: qwen2.5-coder:14b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 48.2%


Problem Breakdown

The problem requires implementing a class NumArray that can efficiently compute the sum of elements in a given range [left, right] of an integer array nums. The key inputs are:

  • An integer array nums during initialization.
  • Two integers left and right for each query.

The output is the sum of the elements from index left to right, inclusive. The constraints include:

  • The length of nums can be up to 10,000.
  • Each element in nums can range from -100,000 to 100,000.
  • There can be up to 10,000 calls to sumRange.

Implicit constraints and edge cases include:

  • Handling empty input arrays.
  • Negative numbers within the array.
  • Multiple queries that may overlap or cover the entire array.

Intuition

A brute-force approach would involve iterating through the subarray from left to right for each query, resulting in a time complexity of O(n) per query. Given that there can be up to 10,000 calls to sumRange, this approach is inefficient and would likely exceed time limits.

The key insight is to preprocess the array during initialization to allow constant-time range sum queries. This can be achieved using prefix sums (also known as cumulative sums). By storing the cumulative sum of elements up to each index, we can compute any range sum in O(1) time by subtracting the appropriate prefix sums.

Approach

  1. Initialization (__init__ method):

    • Create a prefix sum array prefix_sums where prefix_sums[i] stores the sum of elements from the start of the array up to index i.
    • Iterate through the input array nums and compute the cumulative sums, storing them in prefix_sums.
  2. Range Sum Query (sumRange method):

    • To get the sum of elements between indices left and right, use the formula: [ \text{sumRange}(left, right) = prefix_sums[right + 1] - prefix_sums[left] ]
    • If left is 0, simply return prefix_sums[right + 1].

This approach leverages the precomputed prefix sums to answer each query in constant time.

Complexity Analysis

  • Time Complexity:
    • Initialization (__init__ method): O(n), where n is the length of the input array nums.
    • Range Sum Query (sumRange method): O(1) for each query.
  • Space Complexity:
    • O(n) due to the additional storage required for the prefix sums array.

Solution

class NumArray:
    def __init__(self, nums: List[int]):
        # Initialize the prefix sums array with an extra space for easier calculation
        self.prefix_sums = [0] * (len(nums) + 1)
        
        # Compute the prefix sums
        for i in range(len(nums)):
            self.prefix_sums[i + 1] = self.prefix_sums[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        # Return the sum of elements between indices left and right inclusive
        return self.prefix_sums[right + 1] - self.prefix_sums[left]

Edge Cases Handled

  • Empty Array: If nums is empty, the prefix sums array will also be empty. Any query on an empty array will correctly return 0.
  • Single Element Array: The prefix sum for a single-element array will simply be that element itself. Queries on such arrays will handle this naturally.
  • Negative Numbers: The algorithm handles negative numbers correctly by using cumulative sums, which can result in both positive and negative values.
  • Multiple Overlapping Queries: The constant-time query allows handling multiple overlapping or sequential queries efficiently without recalculating sums repeatedly.