Range Sum Query - Immutable

🏠 ⬅️ ➡️

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.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 6
    integer, parameter :: m = 4
    integer, dimension(n) :: nums = [-2, 0, 3, -5, 2, -1]
    integer, dimension(m, 2) :: queries = reshape([0, 2, &
                                                    2, 5, &
                                                    0, 5], shape=[m, 2])
    type(NumArray) :: na
    integer :: i, j

    ! Initialize the NumArray object
    na = NumArray(nums)

    ! Print the results for each query
    do i = 1, size(queries, 1)
        write (unit=error_unit, fmt='(*(g0))') 'Sum of elements between ', &
            queries(i, 1), ' and ', queries(i, 2), ' inclusive: ', &
            na%sumRange(queries(i, 1), queries(i, 2))
    end do

contains

    type NumArray
        private
        integer, allocatable :: nums(:)

        contains
            procedure, public :: sumRange
            generic :: operator(.sum.) => sumRange
    end type NumArray

    interface NumArray
        module procedure :: constructor
    end interface NumArray

    function constructor(nums) result(this)
        implicit none
        integer, intent(in) :: nums(:)
        type(NumArray) :: this

        allocate(this%nums(size(nums)))
        this%nums = nums
    end function constructor

    function sumRange(this, left, right) result(sum)
        implicit none
        class(NumArray), intent(in) :: this
        integer, value :: left, right
        integer :: sum

        sum = sum(this%nums(left:right))
    end function sumRange

end program main
❌ Compiled
❌ Executed
❌ Correct 
module NumArray
    implicit none

    type :: NumArray
        integer, allocatable :: nums(:)
    contains
        procedure :: sumRange
    end type NumArray

    interface NumArray
        module procedure constructor
    end interface NumArray

contains

    function constructor(nums) result(this)
        integer, intent(in) :: nums(:)
        type(NumArray) :: this

        allocate(this%nums(size(nums)))
        this%nums = nums
    end function constructor

    function sumRange(this, left, right) result(sum)
        class(NumArray), intent(in) :: this
        integer, intent(in) :: left, right
        integer :: sum

        sum = sum(this%nums(left:right))
    end function sumRange
end module NumArray

program main
    use NumArray
    implicit none

    integer, parameter :: N = 6
    integer, parameter :: M = 4
    integer :: nums(N) = [-2, 0, 3, -5, 2, -1]
    integer :: queries(M, 2) = reshape([0, 2, 2, 5, 0, 5], shape=[M, 2])
    type(NumArray) :: numArray
    integer :: i, j

    numArray = NumArray(nums)

    do i = 1, M
        write (*, *) numArray%sumRange(queries(i, 1), queries(i, 2))
    end do
end program main
🌐 Data from online sources 
class NumArray:

    def __init__(self, nums: List[int]):
        self.pSum = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.pSum[i + 1] = self.pSum[i] + num

    def sumRange(self, left: int, right: int) -> int:
        return self.pSum[right + 1] - self.pSum[left]

The algorithm uses the concept of prefix-sum to answer range-sum queries efficiently. In the constructor, we iterate through the input nums array and build an additional pSum array, which stores the prefix sum for each position i, i.e., sum of all elements from index 0 to index i (inclusive) of nums.

The sumRange method is simply a matter of taking the difference between two elements in the prefix-sum array. This difference will be the sum of elements between the given left and right indices (inclusive) in the input array.

The algorithm has a time complexity of O(1) for sumRange queries after the O(n) pre-processing of the input array during the constructor call. The space complexity is O(n) for the pSum array.

🌐 Data from online sources 
#include <vector>

class NumArray {
public:
    std::vector<int> pSum;

    NumArray(std::vector<int> &nums) {
        pSum.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++) {
            pSum[i + 1] = pSum[i] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        return pSum[right + 1] - pSum[left];
    }
};

The algorithm uses the concept of prefix-sum to answer range-sum queries efficiently. In the constructor, we iterate through the input nums array and build an additional pSum array, which stores the prefix sum for each position i, i.e., sum of all elements from index 0 to index i (inclusive) of nums.

The sumRange method is simply a matter of taking the difference between two elements in the prefix-sum array. This difference will be the sum of elements between the given left and right indices (inclusive) in the input array.

The algorithm has a time complexity of O(1) for sumRange queries after the O(n) pre-processing of the input array during the constructor call. The space complexity is O(n) for the pSum array.