327. Count Of Range Sum¶

Difficulty: Hard

327. Count of Range Sum

Hard

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¶

public class Solution {
    private int count;
    private int lower;
    private int upper;
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] sum = new long[nums.length + 1];
        long[] temp = new long[nums.length + 1];
        sum[0] = 0;
        this.lower = lower;
        this.upper = upper;
        count = 0;
        for (int i = 1; i <= nums.length; i++) sum[i] = sum[i - 1] + (long)(nums[i - 1]);
        mergesort(sum, 0, sum.length - 1, temp);
        return count;
    }
    private void mergesort(long[] sum, int start, int end, long[] temp) {
        if (start >= end) return;
        int mid = start + (end - start) / 2;
        mergesort(sum, start, mid, temp);
        mergesort(sum, mid + 1, end, temp);
        merge(sum, start, mid, end, temp);
    }
    private void merge(long[] sum, int start, int mid, int end, long[] temp) {
        int right = mid + 1, index = start, low = mid + 1, high = mid + 1;
        for (int left = start; left <= mid; left++) {
            while (low <= end && sum[low] - sum[left] < lower) low++;
            while (high <= end && sum[high] - sum[left] <= upper) high++;
            while (right <= end && sum[right] < sum[left]) temp[index++] = sum[right++];
            temp[index++] = sum[left];
            count += high - low;
        }
        while (right <= end) temp[index++] = sum[right++];
        for (int i = start; i <= end; i++) sum[i] = temp[i];
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here