303. Range Sum Query – ImmutableLeetCode Solution

In this guide, you will get 303. Range Sum Query – ImmutableLeetCode Solution with the best time and space complexity. The solution to Range Sum Query – Immutable problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Range Sum Query – Immutable solution in C++
4. Range Sum Query – Immutable solution in Java
5. Range Sum Query – Immutable solution in Python
6. Additional Resources

Problem Statement of 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.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

303. Range Sum Query – ImmutableLeetCode Solution in C++

class NumArray {
 public:
  NumArray(vector<int>& nums) : prefix(nums.size() + 1) {
    partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);
  }

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

 private:
  vector<int> prefix;
};
/* code provided by PROGIEZ */

303. Range Sum Query – ImmutableLeetCode Solution in Java

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

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

  private int[] prefix;
}
// code provided by PROGIEZ

303. Range Sum Query – ImmutableLeetCode Solution in Python

class NumArray:
  def __init__(self, nums: list[int]):
    self.prefix = list(itertools.accumulate(nums, initial=0))

  def sumRange(self, left: int, right: int) -> int:
    return self.prefix[right + 1] - self.prefix[left]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.