algoadvance

Leetcode 303. Range Sum Query

Problem Statement

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 and right are non-negative integers and 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

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

Clarifying Questions

1. Are the input array elements bounded by any constraints (such as range of values)?
   • Typically in such problems, the array elements can be as large as the language allows for int type in C++.
2. How frequent are the sumRange queries?
   • Usually, for such problems, multiple sumRange queries are expected. We should optimize for multiple queries after initial preprocessing.
3. What should be the behavior if left or right are out of bounds?
   • We can assume that the problem statement will ensure left and right are within valid bounds and left <= right.

Strategy

To efficiently answer the sum queries, we use the concept of prefix sums. This allows us to preprocess the array and then answer any range sum query in constant time O(1).

Steps:

1. Preprocessing (O(n)):
   • Create a prefix sum array prefixSums where prefixSums[i] holds the sum of the array from the start up to the i-th index.
   • This can be computed in a single pass over the array.
2. Query (O(1)):
   • For any query (left, right), the sum can be obtained using prefixSums[right + 1] - prefixSums[left].

Code

#include <vector>
using namespace std;

class NumArray {
private:
    vector<int> prefixSums;
    
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        prefixSums.resize(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefixSums[i + 1] = prefixSums[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return prefixSums[right + 1] - prefixSums[left];
    }
};

Time Complexity

• Preprocessing Time: O(n) where n is the number of elements in nums.
• Query Time: O(1) for each sumRange query.
• Space Complexity: O(n) for storing the prefix sums.

This ensures that after a linear time preprocessing, each range sum query can be answered in constant time, making the overall approach highly efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?