Jobs

Interviews

Discussions

Count of Range Sum

Hard

Asked by:

11 views

Topics:

ArraysRecursion

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
-10⁵ <= lower <= upper <= 10⁵
The answer is guaranteed to fit in a 32-bit integer.

Count of Range Sum

Hard

Asked by:

11 views

Topics:

ArraysRecursion

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
-10⁵ <= lower <= upper <= 10⁵
The answer is guaranteed to fit in a 32-bit integer.

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 possible ranges for the numbers within the input array?
Can the input array be empty or null?
What should I return if no such range exists whose sum falls within the given lower and upper bounds?
Are the lower and upper bounds inclusive or exclusive?
Is the order of the subarrays important? I am assuming that the subarray (i, j) and (j, i) are considered distinct if i !=j and both fall within the range.

Brute Force Solution

Approach

We need to find all groups of numbers that add up to a value within a certain range. The brute force method does this by checking every possible group of numbers, one at a time.

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

First, consider a group containing only the very first number in the list.
Calculate the sum of this group. Check if this sum is within the desired range.
Next, consider a group made up of the first two numbers.
Calculate the sum of this new group, and again check if it falls within the range.
Continue adding one more number to the group at a time, calculating the sum and checking the range each time, until you have a group containing all the numbers in the list.
Now, start over, but this time begin with a group made up of only the second number in the list.
Repeat the process of adding one more number to the group, calculating the sum, and checking the range, just like before.
Keep doing this, starting with each number in the list as the beginning of a new group, and extending each group to include all the numbers that come after it.
Every time you calculate a group's sum, check if that sum is within the specified range. If it is, count it.
After checking all possible groups, the total count of the groups with sums in the correct range is your final answer.

Code Implementation

def count_range_sum_brute_force(numbers, lower_bound, upper_bound):
    number_of_sums_in_range = 0

    # Iterate through all possible starting indices.
    for starting_index in range(len(numbers)):
        current_sum = 0

        # Iterate through all possible ending indices starting from the current start index.
        for ending_index in range(starting_index, len(numbers)):
            current_sum += numbers[ending_index]

            # Check if the current sum falls within the specified range.
            if lower_bound <= current_sum <= upper_bound:
                number_of_sums_in_range += 1

    return number_of_sums_in_range

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force algorithm iterates through all possible subarrays of the input array of size n. For each starting index i from 0 to n-1, it computes the sum of all subarrays starting at i. The inner loop that calculates the sum and checks the range iterates up to n-i times. Therefore, the total number of operations is proportional to n + (n-1) + (n-2) + ... + 1, which is the sum of an arithmetic series. This sum is equivalent to n*(n+1)/2, simplifying to a time complexity of O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach that iterates through all possible subarrays using nested loops. It calculates the sum of each subarray on the fly and checks if it falls within the given range. The only auxiliary space used is for storing a few variables like the current subarray sum and loop counters, which do not depend on the input size N (the number of elements in the list). Therefore, the space complexity is constant.

Optimal Solution

Approach

To efficiently count range sums within a specific range, we'll use a divide-and-conquer strategy inspired by a sorting algorithm. Instead of checking every possible range individually, we cleverly split the problem into smaller subproblems, solve them, and then merge the results while counting the desired range sums.

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

First, calculate the cumulative sum of the numbers, which helps in quickly determining the sum between any two positions.
Then, divide the entire range of numbers into two equal halves.
Recursively apply the same process to the left half and right half until you reach the base case where each half contains only one number. At that point, you're done.
Now, focus on combining the results from the two halves. The key is to count the range sums that start in the left half and end in the right half. Sums completely inside the left or right sub-arrays have already been counted in previous steps.
For each starting point in the left half, efficiently find the range of ending points in the right half such that the sum between those points falls within the specified lower and upper bounds.
Because the cumulative sums are sorted in each half during the merging step (a consequence of using an algorithm inspired by merge sort), we can avoid re-calculating sums already within bounds.
By carefully counting these range sums during the merge process, and combining the results of the subproblems, we obtain the total count of range sums within the desired range efficiently.

Code Implementation

def count_range_sum(numbers, lower_bound, upper_bound):
    prefix_sums = [0]
    for number in numbers:
        prefix_sums.append(prefix_sums[-1] + number)

    def merge_sort_and_count(left, right):
        if left >= right:
            return 0

        middle = (left + right) // 2
        count = merge_sort_and_count(left, middle) + merge_sort_and_count(middle + 1, right)

        # Indices for counting range sums.
        lower_index = middle + 1
        upper_index = middle + 1

        for left_index in range(left, middle + 1):
            while lower_index <= right and prefix_sums[lower_index] - prefix_sums[left_index] < lower_bound:
                lower_index += 1
            while upper_index <= right and prefix_sums[upper_index] - prefix_sums[left_index] <= upper_bound:
                upper_index += 1

            #Accumulate the range of valid indices on the right.
            count += upper_index - lower_index

        #Sort the prefix sums for the merge step.
        prefix_sums[left:right+1] = sorted(prefix_sums[left:right+1])
        return count

    # Initiate the merge sort and count process.
    return merge_sort_and_count(1, len(numbers))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm utilizes a divide-and-conquer approach similar to merge sort. The input array of size n is recursively divided into halves, resulting in a recursion depth of log n. During the merge step, for each element in the left half, we efficiently find the range of elements in the right half that satisfy the sum condition, which can be done in linear time, O(n), due to the sorted nature of the cumulative sums. Therefore, the overall time complexity is O(n log n) because we do O(n) work at each of the O(log n) levels of recursion.

Space Complexity

O(N) – The algorithm uses an auxiliary array of size N to store the cumulative sums. Additionally, the merge sort-inspired process implicitly creates temporary arrays during the merging step, also of size up to N in each level of recursion. Although the depth of recursion is log(N), at each level, the merging process requires O(N) space. Therefore, the overall space complexity is dominated by the auxiliary cumulative sum array and temporary arrays used during merge sort, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no subarrays to consider.
lower bound greater than upper bound	Return 0, because no sums can fall within a nonexistent range.
Input array contains only zeros	The prefix sum array will consist only of zeros, so the number of valid ranges will depend entirely on the lower and upper bounds.
Input array contains only positive numbers and lower bound is positive	The prefix sums will be monotonically increasing, so binary search or two pointers can efficiently find valid ranges.
Integer overflow in prefix sums (especially with large arrays or large numbers)	Use 64-bit integers (long in Java/C++) to store prefix sums to prevent overflow.
Large input array causing memory issues (prefix sum array will be the same size as input)	Consider divide-and-conquer approaches like merge sort to process the array in smaller chunks.
lower and upper bounds are both 0	The solution should accurately count the number of subarrays whose sum is exactly 0.
Input array contains very large positive and very large negative numbers that cancel each other out	The algorithm should handle large swings in prefix sums correctly.

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 possible ranges for the numbers within the input array?
Can the input array be empty or null?
What should I return if no such range exists whose sum falls within the given lower and upper bounds?
Are the lower and upper bounds inclusive or exclusive?
Is the order of the subarrays important? I am assuming that the subarray (i, j) and (j, i) are considered distinct if i !=j and both fall within the range.

Brute Force Solution

Approach

We need to find all groups of numbers that add up to a value within a certain range. The brute force method does this by checking every possible group of numbers, one at a time.

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

First, consider a group containing only the very first number in the list.
Calculate the sum of this group. Check if this sum is within the desired range.
Next, consider a group made up of the first two numbers.
Calculate the sum of this new group, and again check if it falls within the range.
Continue adding one more number to the group at a time, calculating the sum and checking the range each time, until you have a group containing all the numbers in the list.
Now, start over, but this time begin with a group made up of only the second number in the list.
Repeat the process of adding one more number to the group, calculating the sum, and checking the range, just like before.
Keep doing this, starting with each number in the list as the beginning of a new group, and extending each group to include all the numbers that come after it.
Every time you calculate a group's sum, check if that sum is within the specified range. If it is, count it.
After checking all possible groups, the total count of the groups with sums in the correct range is your final answer.

Code Implementation

def count_range_sum_brute_force(numbers, lower_bound, upper_bound):
    number_of_sums_in_range = 0

    # Iterate through all possible starting indices.
    for starting_index in range(len(numbers)):
        current_sum = 0

        # Iterate through all possible ending indices starting from the current start index.
        for ending_index in range(starting_index, len(numbers)):
            current_sum += numbers[ending_index]

            # Check if the current sum falls within the specified range.
            if lower_bound <= current_sum <= upper_bound:
                number_of_sums_in_range += 1

    return number_of_sums_in_range

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, calculate the cumulative sum of the numbers, which helps in quickly determining the sum between any two positions.
Then, divide the entire range of numbers into two equal halves.
Recursively apply the same process to the left half and right half until you reach the base case where each half contains only one number. At that point, you're done.
Now, focus on combining the results from the two halves. The key is to count the range sums that start in the left half and end in the right half. Sums completely inside the left or right sub-arrays have already been counted in previous steps.
For each starting point in the left half, efficiently find the range of ending points in the right half such that the sum between those points falls within the specified lower and upper bounds.
Because the cumulative sums are sorted in each half during the merging step (a consequence of using an algorithm inspired by merge sort), we can avoid re-calculating sums already within bounds.
By carefully counting these range sums during the merge process, and combining the results of the subproblems, we obtain the total count of range sums within the desired range efficiently.

Code Implementation

def count_range_sum(numbers, lower_bound, upper_bound):
    prefix_sums = [0]
    for number in numbers:
        prefix_sums.append(prefix_sums[-1] + number)

    def merge_sort_and_count(left, right):
        if left >= right:
            return 0

        middle = (left + right) // 2
        count = merge_sort_and_count(left, middle) + merge_sort_and_count(middle + 1, right)

        # Indices for counting range sums.
        lower_index = middle + 1
        upper_index = middle + 1

        for left_index in range(left, middle + 1):
            while lower_index <= right and prefix_sums[lower_index] - prefix_sums[left_index] < lower_bound:
                lower_index += 1
            while upper_index <= right and prefix_sums[upper_index] - prefix_sums[left_index] <= upper_bound:
                upper_index += 1

            #Accumulate the range of valid indices on the right.
            count += upper_index - lower_index

        #Sort the prefix sums for the merge step.
        prefix_sums[left:right+1] = sorted(prefix_sums[left:right+1])
        return count

    # Initiate the merge sort and count process.
    return merge_sort_and_count(1, len(numbers))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no subarrays to consider.
lower bound greater than upper bound	Return 0, because no sums can fall within a nonexistent range.
Input array contains only zeros	The prefix sum array will consist only of zeros, so the number of valid ranges will depend entirely on the lower and upper bounds.
Input array contains only positive numbers and lower bound is positive	The prefix sums will be monotonically increasing, so binary search or two pointers can efficiently find valid ranges.
Integer overflow in prefix sums (especially with large arrays or large numbers)	Use 64-bit integers (long in Java/C++) to store prefix sums to prevent overflow.
Large input array causing memory issues (prefix sum array will be the same size as input)	Consider divide-and-conquer approaches like merge sort to process the array in smaller chunks.
lower and upper bounds are both 0	The solution should accurately count the number of subarrays whose sum is exactly 0.
Input array contains very large positive and very large negative numbers that cancel each other out	The algorithm should handle large swings in prefix sums correctly.