Count Subarrays With Fixed Bounds - Leetcode Solution

Problem Statement:

Given an array of integers nums and two integers lower and upper, find the number of contiguous subarrays whose sum lies within the range [lower, upper].

Example:

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

Solution:

The given problem can be solved using Divide and Conquer approach. We start by dividing the given array into two parts, left and right.

We recursively find all the subarrays whose sum lies within [lower, upper] range in the left and right parts. To find subarrays in the left part, we need to consider all the subarrays that end at an element in the left part. Similarly, to find subarrays in the right part, we need to consider all the subarrays that start at an element in the right part.

Now, let's focus on finding all the subarrays that end at an element in the left part. To do this, we traverse through the left part of the array and maintain a prefix sum. At each element, we check if the prefix sum lies within the [lower, upper] range. To find all subarrays that end at this element, we check how many prefix sums lie within the range [prefix_sum - upper, prefix_sum - lower]. We can use a binary search to find the number of prefix sums in this range.

Similarly, to find all subarrays that start at an element in the right part, we traverse through the right part of the array and maintain a suffix sum. At each element, we check if the suffix sum lies within the [lower, upper] range. To find all subarrays that start at this element, we check how many suffix sums lie within the range [suffix_sum - upper, suffix_sum - lower]. We can use a binary search to find the number of suffix sums in this range.

Finally, we add up the count of subarrays found in the left and right parts of the array to get the total count of subarrays whose sum lies within the given range.

Let's look at the implementation of the above approach:

public class Solution { public int countRangeSum(int[] nums, int lower, int upper) { int n = nums.length; long[] prefixSum = new long[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } return countSubarrays(prefixSum, 0, n, lower, upper); }

private int countSubarrays(long[] prefixSum, int left, int right, int lower, int upper) {
    if (right - left <= 1) {
        return 0;
    }
    
    int mid = left + (right - left) / 2;
    int count = countSubarrays(prefixSum, left, mid, lower, upper) 
              + countSubarrays(prefixSum, mid, right, lower, upper);
    
    int i = left, j = mid, k = mid;
    long[] merged = new long[right - left];
    int t = 0;
    while (i < mid) {
        while (j < right && prefixSum[j] - prefixSum[i] < lower) {
            j++;
        }
        while (k < right && prefixSum[k] - prefixSum[i] <= upper) {
            k++;
        }
        count += k - j;
        
        while (t < right - left && prefixSum[i] > prefixSum[j]) {
            merged[t++] = prefixSum[j++] - prefixSum[left];
        }
        merged[t++] = prefixSum[i++] - prefixSum[left];
    }
    
    System.arraycopy(merged, 0, prefixSum, left, t);
    return count;
}

}

The above solution has a time complexity of O(nlogn) and space complexity of O(n).

1