Range Sum Query Immutable - Leetcode Solution

Problem statement:

Given an integer array nums, find the sum of the elements between indices left and right inclusive, where (0 ≤ left ≤ right < n).

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 the nums array in the range [left, right] inclusive (i.e., sum(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]

Explanation NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

Solution:

The basic idea of this problem is to pre-process the input array so that we can find the sum of elements in any given range in constant time. We can achieve this by maintaining an auxiliary array of the same size as the input array, where each element represents the sum of elements from the beginning of the input array up to that index.

Let's call this auxiliary array as prefix_sum. The value at index i in prefix_sum is the sum of elements in nums from index 0 to i. For example, if nums is [1,2,3,4,5], then prefix_sum would be [1,3,6,10,15].

Once we have this prefix_sum array, we can compute the sum of elements in any given range [left,right] by simply subtracting prefix_sum[left-1] from prefix_sum[right], since the value at prefix_sum[left-1] represents the sum of elements from index 0 to left-1, which needs to be subtracted from the sum of elements from index 0 to right to get the sum of elements in the range [left,right].

Here is the implementation of the NumArray class in Java:

class NumArray { private int[] prefix_sum; // auxiliary array public NumArray(int[] nums) { int n = nums.length; prefix_sum = new int[n]; prefix_sum[0] = nums[0]; for (int i = 1; i < n; i++) { prefix_sum[i] = prefix_sum[i-1] + nums[i]; } }

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

}

Time Complexity:

The time complexity of the NumArray constructor is O(n), where n is the length of the input array. This is because we need to iterate through the entire input array to compute the prefix_sum array.

The time complexity of the sumRange method is O(1), since we are simply subtracting two elements from the prefix_sum array.

Space Complexity:

The space complexity of the NumArray class is O(n), since we need to store the prefix_sum array of the same size as the input array.

1