problemeasyalgorithmsleetcode-303leetcode 303leetcode303daily-coding-problem-149daily coding problem 149dailycodingproblem149

Range Sum Query - Immutable

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Given an integer array nums, handle multiple queries of the following type:

  1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

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 the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Examples

Example 1:

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

Solution

Method 1 - Prefix Sum

To efficiently compute the sum of elements between two indices for multiple queries, we can precompute prefix sums. This allows us to retrieve the sum for any range in constant time.

Approach

  1. Precompute Prefix Sums: Before answering any queries, compute the cumulative sum up to each index in the array.
  2. Use Prefix Sums for Queries: The sum from index left to right can be obtained by subtracting the prefix sum up to left-1 from the prefix sum up to right.

Code

Java
class NumArray {
    private int[] prefixSums;

    public NumArray(int[] nums) {
        int n = nums.length;
        prefixSums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefixSums[right + 1] - prefixSums[left];
    }
}
Python
class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix_sums = [0] * (len(nums) + 1)
        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 self.prefix_sums[right + 1] - self.prefix_sums[left]

Complexity

  • ⏰ Time complexity: - O(n) for computing prefix sums where n is the length of the array.
  • Query: O(1) for each sumRange query.
  • 🧺 Space complexity: O(n) for storing the prefix sums.

Comments