algoadvance

The problem “303. Range Sum Query - Immutable” on LeetCode is defined as follows:

Given an integer array nums, 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]).

Clarifying Questions

1. Q: Can the nums array be empty?
   • A: Yes, an empty array is a valid input.
2. Q: What are the constraints on the integer values in the array?
   • A: The integer values are within the range of -10^5 to 10^5.
3. Q: What is the size range of the nums array?
   • A: The array length can be from 0 to 10^4.
4. Q: How frequently will the sumRange queries be called?
   • A: The frequency isn’t specified, but we should optimize for multiple calls.

Strategy

Given that the array is immutable and we need to support multiple sumRange queries efficiently, we should use a preprocessing approach to create a prefix sum array. This approach will allow us to answer each range sum query in constant time (O(1)).

Steps:

1. Preprocessing:
   • Build a prefix sum array where prefix[i] is the sum of the elements from nums[0] to nums[i-1] (with prefix[0] = 0).
   • This allows us to compute any range sum sumRange(left, right) as prefix[right + 1] - prefix[left].
2. Query:
   • For each sumRange(left, right) query, use the precomputed prefix sums to get the result in constant time.

Code

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.prefix_sums = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix_sums[i + 1] = self.prefix_sums[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix_sums[right + 1] - self.prefix_sums[left]

Time Complexity

• Preprocessing Time: (O(n)), where (n) is the length of the input array nums. This is for building the prefix sum array.
• Space Complexity: (O(n)), for storing the prefix sums.
• Query Time: (O(1)) per query, since each sumRange operation is computed using the prefix sums in constant time.

This solution efficiently preprocesses the data to allow each range sum query to be answered in constant time, leveraging extra space for the prefix sum array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?