Array Design Prefix Sum

Leetcode Link for 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

Constraints:

  • 1 <= nums.length <= 104

  • -105 <= nums[i] <= 105

  • 0 <= left <= right < nums.length

  • At most 104 calls will be made to sumRange.

Solution:


class NumArray {
    int runningSum=0;
    int [] prefixSum;
    public NumArray(int[] nums) {
        prefixSum = new int[nums.length];
        for(int i=0; i < nums.length; i++){
            runningSum += nums[i];
            prefixSum[i] = runningSum;
        }

    }
    
    public int sumRange(int left, int right) {
        if(left == 0)
            return prefixSum[right];
        
        return prefixSum[right] - prefixSum[left -1];
        
    }
}

Github Link: https://github.com/miqbal3636/problem_solving/blob/main/src/com/spsoft/leetcode/easy/array/NumArray.java

Explanation:

1. Initialization: The constructor initializes the prefixSum array, which takes O(n) time where n is the length of the input array nums. This ensures that each index i in prefixSum holds the sum of all elements from the start of nums up to i.

2. sumRange Method: The sumRange method uses the prefixSum array to compute the sum of elements between indices left and right in constant time O(1). The method checks if left is 0, then directly returns prefixSum[right]. If left is not 0, it calculates the range sum by subtracting prefixSum[left - 1] from prefixSum[right].

Time complexity:

Constructor: O(n)

sumRange Method: O(1)

Space complexity: O(n)

This design ensures that the sumRange operation is very efficient, with a constant time complexity. The trade-off is the linear time complexity during initialization and the space complexity O(n) for storing the prefix sums.

Author: Mohammad J Iqbal

Mohammad J Iqbal

Follow Mohammad J Iqbal on LinkedIn