Scale Engineer

Range Sum Query - Immutable

Easy
#0290Time: O(n) per query, where n is the length of the range (right - left + 1). Constructor: O(1)Space: O(1) additional space (only storing reference to original array)1 company
Patterns
DesignPrefix Sum
Data structures
Array
Companies
Palantir Technologies

Prompt

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

 

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 <= 104
  • -105 <= nums[i] <= 105
  • 0 <= left <= right < nums.length
  • At most 104 calls will be made to sumRange.

Approaches

2 approaches with complexity analysis and trade-offs.

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

  1. Store the original array in the constructor
  2. 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

Walkthrough

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

Time

O(n) per query, where n is the length of the range (right - left + 1). Constructor: O(1)

Space

O(1) additional space (only storing reference to original array)

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem