Range Sum Query - Immutable

EASY

Description

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

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]).

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

Constraints:

1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= left <= right < nums.length
At most 10⁴ calls will be made to sumRange.

Approaches

Checkout 2 different approaches to solve Range Sum Query - Immutable. Click on different approaches to view the approach and algorithm in detail.

Brute Force - Calculate Sum for Each Query

The most straightforward approach is to calculate the sum for each query by iterating through the range from left to right index. This approach doesn't require any preprocessing but has poor performance for multiple queries.

Algorithm

Store the original array in the constructor
For each sumRange(left, right) query:
- Initialize sum to 0
- Iterate from index left to right
- Add each element to the sum
- Return the accumulated sum

For each sumRange(left, right) query, we iterate through the array from index left to right and accumulate the sum. This is the most naive approach where we don't store any additional information and compute the sum fresh for every query.

class NumArray {
    private int[] nums;
    
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

This approach is simple to implement but becomes inefficient when we have many queries, especially for large ranges.

Complexity Analysis

Time Complexity: O(n) per query, where n is the length of the range (right - left + 1). Constructor: O(1)Space Complexity: O(1) additional space (only storing reference to original array)

Pros and Cons

Pros:

Simple to understand and implement
No additional space required beyond storing the original array
No preprocessing time needed

Cons:

Inefficient for multiple queries
Time complexity grows linearly with range size
Redundant calculations for overlapping ranges

Code Solutions

Checking out 4 solutions in different languages for Range Sum Query - Immutable. Click on different languages to view the code.

class NumArray { private int [] s ; public NumArray ( int [] nums ) { int n = nums . length ; s = new int [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } } public int sumRange ( int left , int right ) { return s [ right + 1 ] - s [ left ]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */

Video Solution

Watch the video walkthrough for Range Sum Query - Immutable

Patterns:

DesignPrefix Sum

Data Structures:

Array

Companies:

Palantir Technologies |