303. Range Sum Query - Immutable

Description

The problem involves implementing a class NumArray that can efficiently calculate the sum of elements in a given range of an integer array. The class should have a constructor that initializes the array and a method sumRange(left, right) that returns the sum of elements between the indices left and right (inclusive).

Intuition

The straightforward way to calculate the sum of elements between two indices is to iterate through the array from left to right and accumulate the sum. This approach is simple and intuitive but may not be the most efficient for repeated queries.

Approach

1. Initialization: Store the array nums when initializing the NumArray object.
2. Calculate Range Sum: The sumRange method iterates through the array elements from index left to right and computes the sum. This method provides a direct solution to calculate the sum in the specified range.
3. Optimization Considerations: While this approach is straightforward, it may be inefficient for large arrays with frequent sum queries. To optimize, we might consider preprocessing the array to enable faster range sum queries (e.g., using a prefix sum array), but this is not covered in the current implementation.

Complexity

Time Complexity:

The time complexity for each sumRange query is (O(n)), where (n) is the number of elements between left and right. This linear time complexity could be a drawback for large arrays with many queries.

Space Complexity:

The space complexity is (O(1)) beyond the space required to store the input array nums. No additional space is used apart from the input array.

Code

C++

class NumArray {
public:
    NumArray(std::vector& nums) {
        this->nums = nums;
    }

    int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; ++i) {
            sum += nums[i];
        }
        return sum;
    }

private:
    std::vector nums;
};

Python

class NumArray:
    def __init__(self, nums):
        self.nums = nums

    def sumRange(self, left, right):
        return sum(self.nums[left:right+1])

Java

public class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

JavaScript

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
var NumArray = function(nums) {
    this.nums = nums;
};

NumArray.prototype.sumRange = function(left, right) {
    let sum = 0;
    for(let i = left; i <= right; i++) sum += this.nums[i]
    return sum
};