August leetcoding Challenge 2021 - Range Sum Query - Immutable

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

Link to question on leetcode

Bruteforce approach

The bruteforce solution for this question would , when ever a sumRange query is called compute the sum from given start and end index and return the sum.

Time complexity for this approach will be O(number of time function called * n) - here we are computing the sum for every query

Optimized solution

Instead of calculating the sum for every query , we can have a precomputed sum array , where prefix[i] will be the sum of array from 0 to i . Using this precomputed array for every query we can return the sum in O(1) time complexity.

Psuedo code

• Created a prefix array of size of the given array.
• Compute the prefix array where prefix[i] will give the sum of array from 0 to i(inclusive)
• Now for every query requested , do the following:
  1. If left is 0 , directly return prefix[right]
  2. else return prefix[right] - prefix[left-1] - because prefix of right will be sum of original array from 0 to right , so we have to substract sum of array from 0 to left-1 from prefix[right]

Code

class NumArray:
    def __init__(self, nums: List[int]):
        self.length = len(nums)
        self.prefixsum = [0]*self.length
        self.prefixsum[0] = nums[0]
        for i in range(1,self.length):
            self.prefixsum[i] = self.prefixsum[i-1]+nums[i]
        self.total = self.prefixsum[-1]


    def sumRange(self, left: int, right: int) -> int:
        if left == 0:
            return self.prefixsum[right]
        return self.prefixsum[right]-self.prefixsum[left-1]

Please like this post and share if you found this post helpful.