NUHMAN.com

Introduction

LeetCode 303: Range Sum Query - Immutable asks us to design a data structure that allows us to efficiently compute the sum of elements between indices in a given immutable integer array. The array is initialized at the beginning, and after that, we need to process multiple range sum queries. The goal is to optimize these range sum queries to be as efficient as possible.

We will achieve this by precomputing the prefix sums, which can then be used to compute any range sum in constant time.

Problem Statement

Given an integer array nums, implement a data structure that supports the following two operations:

1. sumRange(i, j): Return the sum of the elements of nums between indices i and j inclusive.
2. Constructor(nums): Initializes the data structure with the given integer array nums.

Example

python

# 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 1 ((-2) + 0 + 3 = 1)
# numArray.sumRange(2, 5); -> return -1 (3 + (-5) + 2 + (-1) = -1)
# numArray.sumRange(0, 5); -> return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1) = -3)

✅ Step-by-Step Solution

🧠 Intuition

To solve this problem efficiently, we can use the prefix sum technique. The idea is to precompute an array where each element at index i stores the sum of all elements in the input array up to that index. With this array, we can compute any range sum in constant time by using the formula:

sumRange(i,j)=prefix[j+1]−prefix[i]\text{sumRange}(i, j) = \text{prefix}[j + 1] - \text{prefix}[i]sumRange(i,j)=prefix[j+1]−prefix[i]Where:

• prefix[i] represents the sum of all elements from index 0 to index i-1.
• By subtracting prefix[i] from prefix[j + 1], we get the sum of elements between indices i and j inclusive.

This allows us to handle range sum queries in constant time after an initial preprocessing step.

✅ Approach

1. Initialization:

• Compute a prefix sum array where each element at index i holds the sum of elements from index 0 to i-1.
• This allows for quick access to the sum of any range.

1. sumRange Calculation:

• To calculate the sum of elements between indices i and j, simply subtract the prefix sum at i from the prefix sum at j + 1.

1. Optimization:

• The initialization of the prefix sum array takes O(n) time.
• Each query (sumRange) takes O(1) time due to the precomputed prefix sum.

✅ Python Code

python

class NumArray:

    def __init__(self, nums: list[int]):
        # Initialize the prefix sum array
        self.prefix = [0] * (len(nums) + 1)
        
        # Build the prefix sum array
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def sumRange(self, i: int, j: int) -> int:
        # Return the sum between indices i and j inclusive
        return self.prefix[j + 1] - self.prefix[i]

🧪 How It Works

1. Constructor:

• The NumArray class is initialized with a list of integers nums.
• We then build the prefix sum array where each element at index i stores the sum of the elements from nums[0] to nums[i-1].

1. sumRange Function:

• The sumRange(i, j) function uses the prefix sum array to calculate the sum of the elements between indices i and j in constant time by subtracting prefix[i] from prefix[j + 1].

1. Efficiency:

• Initialization: The prefix sum array is built in O(n) time.
• Query: Each query (sumRange) takes O(1) time due to the precomputed prefix sum array.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n) for initialization, O(1) per querySpace ComplexityO(n)

• Time Complexity (Initialization): Building the prefix sum array takes O(n) time, where n is the length of the input array nums.
• Time Complexity (sumRange): Each query is answered in constant time O(1) since it involves a simple subtraction between two elements of the prefix sum array.
• Space Complexity: We need O(n) extra space to store the prefix sum array, where n is the length of the input array.

🔍 Edge Cases

1. Empty Array:

• If the input array is empty, the result for any query should be 0, and the prefix array will only contain a single element [0].

1. Single Element Array:

• If the input array contains only one element, the sum of that element from index 0 to 0 will simply be that element.

1. Multiple Queries:

• The sumRange function should handle multiple queries efficiently, even if the array is large, since each query takes constant time after initialization.

✅ Conclusion

LeetCode 303: Range Sum Query - Immutable is a problem that can be solved efficiently by utilizing the prefix sum technique. By precomputing the prefix sums, we reduce the time complexity for each range sum query to O(1), which is optimal for large input sizes.

• The initialization of the prefix sum array takes O(n) time, and each sumRange query is answered in O(1) time, making this approach highly efficient for multiple queries.

This solution is ideal when we need to process many range sum queries on an immutable array.