Range Sum Query - Immutable

Patrick Leaton
Published: March 28, 2021, 11:22 p.m.
Problem Description

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

 

The description was taken from https://leetcode.com/problems/range-sum-query-immutable/.

Problem Solution

#O(N) Initialization and O(1) Query Time
#O(N) Space
class NumArray:
    def __init__(self, nums: List[int]) -> None:
        self.dp = [0] * (len(nums) + 1)
        for i in range(0, len(nums)):
            self.dp[i+1] = self.dp[i] + nums[i]
 
    def sumRange(self, left: int, right: int) -> int:
        return self.dp[right+1] - self.dp[left]

Problem Explanation

The brute force method of solving this problem would be to simply calculate the sum range between the two inputs i and j.  

However, with this approach, we could possibly be recalculating results that have been calculated before, given a great number of function calls.

What we could do to avoid this repetitive work is to cache the running sum from the input values, so that the results can be given in constant time.

This pattern is known as a Prefix Sum.

A hint for knowing when to apply this pattern is when a question will require us to make several operations over a range of a list.

Let's start by initializing our dp array.

The value of the first index we will keep is zero.  We do this because we are storing the cumulative sums for each index in dp and initially, the sum would be zero.  This is the base case.

        self.dp = [0] * (len(nums) + 1)

 

For every index in our dp cache starting after the base case, we will set the value as the current value within the input array plus the current running sum we have stored in our cache.  

        for i in range(0, len(nums)):
            self.dp[i+1] = self.dp[i] + nums[i]

 

If our input looks like the example given in the problem description:

[-2, 0, 3, -5, 2, -1]

Us storing the running sum in our cache will look like this for each iteration:

[0, -2, 0, 0, 0, 0, 0]
[0, -2, -2, 0, 0, 0, 0]
[0, -2, -2, 1, 0, 0, 0]
[0, -2, -2, 1, -4, 0, 0]
[0, -2, -2, 1, -4, -2, 0]
[0, -2, -2, 1, -4, -2, -3]
 

We can see that we have stored within each index a predetermined answer to the subproblem for each query within the range equal to the length of the input array.

After we have cached all of these values, we can return the sum range between the two inputs left and right by returning the difference of the right place, plus one since we have a base case and the left place within our dp array.

If we were asked the sum range between five and three from the input: [-2, 0, 3, -5, 2, -1], we can see adding these together would equal negative four.

We would have that result in constant time within our dp cache by subtracting the element at the right pointer with the left: [0, -2, -2, 1, -4, -2, -3]. 

        return self.dp[right+1] - self.dp[left]