Algorithm

Problem Name: 303. Range Sum Query - Immutable

Problem Link: https://leetcode.com/problems/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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class NumArray {
public:
    NumArray(vector<int> nums) {
        int sum = 0;
        for(auto x: nums){
            sum += x;
            dp.push_back(sum);
        }
    }
    
    int sumRange(int i, int j) {
        return i == 0 ? dp[j] : dp[j] - dp[i - 1];
    }
    
private:
    vector<int>dp;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

x
–
+
cmd
[null, 1, -1, -3]

#2 Code Example with Java Programming

Code - Java Programming


class NumArray {

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

  public int sumRange(int left, int right) {
    return sumArray[right] - (left == 0 ? 0 : sumArray[left - 1]);
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

x
–
+
cmd
[null, 1, -1, -3]

#3 Code Example with Python Programming

Code - Python Programming


class NumArray:

    def __init__(self, nums):
        self.nums = nums
        for i in range(1, len(nums)):
            self.nums[i] += self.nums[i - 1]
        

    def sumRange(self, i, j):
        return self.nums[j] - self.nums[i - 1] if i else self.nums[j]
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

x
–
+
cmd
[null, 1, -1, -3]

#4 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0303_RangeSumQueryImmutable
    {
        private readonly int[] sums;

        public _0303_RangeSumQueryImmutable(int[] nums)
        {
            sums = new int[nums.Length];

            var sum = 0;
            for (int i = 0; i  <  nums.Length; i++)
            {
                sum += nums[i];
                sums[i] = sum;
            }
        }

        public int SumRange(int i, int j)
        {
            if (i == 0)
                return sums[j];
            else
                return sums[j] - sums[i - 1];
        }
    }
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

x
–
+
cmd
[null, 1, -1, -3]
Advertisements

Demonstration

Previous
#301 Leetcode Remove Invalid Parentheses Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#304 Leetcode Range Sum Query 2D - Immutable Solution in C, C++, Java, JavaScript, Python, C# Leetcode