Range Sum Query - Immutable

Easy

Palantir

4 views

Topics:

ArraysDynamic Programming

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 <= 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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= left <= right < nums.length
At most 10⁴ calls will be made to sumRange.

Range Sum Query - Immutable

Easy

Palantir

4 views

Topics:

ArraysDynamic Programming

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 <= 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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= left <= right < nums.length
At most 10⁴ calls will be made to sumRange.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums`? Is it possible that the array is empty?
What are the possible values within the `nums` array? Can I expect negative integers, zero, or only positive integers?
What are the constraints on `left` and `right`? Are they guaranteed to be within the bounds of the array `nums`, and is `left` always less than or equal to `right`?
How many times will the `sumRange` method be called? Should I optimize for a large number of calls?
Is the input array `nums` mutable after initialization of the `NumArray` object?

Brute Force Solution

Approach

The brute force approach to answering the sum of a range is very simple. We directly calculate the sum for the specific range given. This means we look at each number within the range and add them together.

Here's how the algorithm would work step-by-step:

Identify the starting and ending points of the range we're interested in.
Begin at the starting point and move towards the ending point, one number at a time.
For each number we encounter, add it to a running total.
Once we reach the ending point of the range, the running total is the sum of the range.
Report this final total as the answer.

Code Implementation

class NumArray:

    def __init__(self, numbers):
        self.numbers = numbers

    def sumRange(self, left_index, right_index):
        range_sum = 0

        # Iterate from left_index up to right_index (inclusive)
        for current_index in range(left_index, right_index + 1):
            # Add each number in the range to the total
            range_sum += self.numbers[current_index]

        return range_sum

# Your NumArray object will be instantiated and called as such:
# numbers = [ -2, 0, 3, -5, 2, -1 ]
# obj = NumArray(numbers)
# param_1 = obj.sumRange(0,2)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided brute force approach iterates through the input array nums to calculate the sum of the range [left, right]. In the worst case, the range could encompass the entire array, requiring the algorithm to traverse all 'n' elements. Therefore, the time complexity is directly proportional to the size of the range, making it O(n).

Space Complexity

O(1) – The provided brute force approach calculates the range sum by iterating and accumulating the sum within the given range. It only uses a fixed number of variables: start index, end index, and a running total. The amount of extra memory used does not depend on the input array size (N). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

Instead of recalculating the sum for every query, we will do some pre-processing to make lookups faster. This pre-processing will allow us to answer each query in a constant amount of time.

Here's how the algorithm would work step-by-step:

First, create a new list where each element represents the cumulative sum of all elements up to that point in the original list.
For example, the first element in the new list will be the first element of the original list. The second element in the new list will be the sum of the first two elements of the original list, and so on.
Once we have this new list of cumulative sums, we can quickly calculate the sum between any two points.
To find the sum between a start point and an end point, subtract the cumulative sum just *before* the start point from the cumulative sum at the end point. This gives you the sum of just the values between those two points.
Since we've pre-computed all the cumulative sums, each query only requires one subtraction, which is very fast.

Code Implementation

class NumArray:

    def __init__(self, nums):
        self.original_array = nums
        self.cumulative_sum_array = [0] * (len(nums) + 1)

        # Create cumulative sum array for O(1) queries.
        for index in range(len(nums)):
            self.cumulative_sum_array[index + 1] = self.cumulative_sum_array[index] + nums[index]

    def sumRange(self, left_index, right_index):
        # Subtract sum before left from sum at right.
        return self.cumulative_sum_array[right_index + 1] - self.cumulative_sum_array[left_index]

# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.sumRange(1, 2)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The constructor iterates through the input array nums of size n to compute the cumulative sums and store them in a separate array. This initialization process takes linear time, proportional to the number of elements in the input array. Subsequent calls to the sumRange method perform a single subtraction, which is a constant-time operation. Therefore, the overall time complexity is dominated by the initial cumulative sum calculation, resulting in O(n) complexity.

Space Complexity

O(N) – The provided solution creates a new list to store the cumulative sums of the original list. This new list, which is an auxiliary data structure, will have the same number of elements as the original list, denoted as N. Therefore, the space required for storing the cumulative sums scales linearly with the input size N. Consequently, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array 'nums'	Throw an IllegalArgumentException or return 0 to indicate invalid input in the constructor.
left > right	Return 0 or throw an IllegalArgumentException, as the range is invalid.
left or right are out of bounds (left < 0 or right >= nums.length)	Throw an IndexOutOfBoundsException or adjust the indices to the valid range (e.g., clamp to array boundaries).
Large input array 'nums' (e.g., millions of elements)	Prefix sum approach ensures O(1) time complexity for sumRange, providing good scalability.
Input array contains only negative numbers	The prefix sum approach works correctly regardless of negative values.
Input array contains extreme values (Integer.MAX_VALUE, Integer.MIN_VALUE)	Use long data type for prefix sums to avoid integer overflow during summation.
left == right (single element range)	The algorithm should correctly return the value of nums[left].
Integer overflow in sum calculation if using int for prefix sum with extremely large array values and range	Use long to store prefix sums to prevent integer overflow in sum calculations.