LeetCode 303. Range Sum Query - Immutable

Post by ailswan Dec. 13, 2023

303. Range Sum Query - Immutable

Design, Array, Prefix SUm  · 

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: ["NumArray", "sumRange", "sumRange", "sumRange"][[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output: [null, 1, -1, -3]

Solution Approach

To efficiently handle multiple range sum queries, we can precompute prefix sums of the given array nums.

Algorithm

  1. Initialize the pre_sums list with an initial value of 0 to handle the case when the left index is 0.
  2. Compute the prefix sums of nums by iterating through each element in nums and appending the cumulative sum to pre_sums.
  3. Return the computed sum for each sumRange query.

Implement

    class Solution:
    def __init__(self, nums):
      self.pre_sums = [0]
      _sums = self.pre_sums
      for n in nums:
        _sums.append(_sums[-1] + n)
    def sumRange(self, left, right):
      _sums = self.pre_sums
      return _sums[right + 1] - _sums[left]