LeetCode 327: Count of Range Sum Solution

Master LeetCode problem 327 (Count of Range Sum), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

327. Count of Range Sum

Hard

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

Problem Explanation

Explanation:

To solve this problem, we can use a divide and conquer approach combined with a merge sort strategy. We will maintain a prefix sum array prefixSum where prefixSum[i] represents the sum of all elements from nums[0] to nums[i]. Then, we will recursively divide the array into two halves, count the number of valid ranges that cross the two halves, and merge the sorted halves while updating the count of valid ranges.

Algorithm:
1. Initialize a count variable to store the total count of valid ranges.
2. Create a helper function mergeCount that merges two sorted prefix sum arrays and counts the number of valid ranges that cross the two halves.
3. Implement a recursive function mergeSortCount that divides the array into two halves, recursively counts the valid ranges in each half, and then merges and counts the valid ranges that cross the two halves.
4. Return the count variable.
Time Complexity: O(n log n) where n is the number of elements in the nums array.
Space Complexity: O(n) for the prefix sum array and other auxiliary space used in the merge sort.

Solution Code

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] prefixSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        return mergeSortCount(prefixSum, 0, nums.length, lower, upper);
    }
    
    private int mergeSortCount(long[] prefixSum, int start, int end, int lower, int upper) {
        if (start >= end) return 0;
        
        int mid = start + (end - start) / 2;
        int count = mergeSortCount(prefixSum, start, mid, lower, upper) +
                    mergeSortCount(prefixSum, mid + 1, end, lower, upper);
        
        int j = mid + 1, k = mid + 1;
        int t = mid + 1;
        long[] sorted = new long[end - start + 1];
        
        for (int i = start, r = 0; i <= mid; i++, r++) {
            while (j <= end && prefixSum[j] - prefixSum[i] < lower) j++;
            while (k <= end && prefixSum[k] - prefixSum[i] <= upper) k++;
            while (t <= end && prefixSum[t] < prefixSum[i]) sorted[r++] = prefixSum[t++];
            sorted[r] = prefixSum[i];
            count += k - j;
        }
        
        System.arraycopy(sorted, 0, prefixSum, start, t - start);
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 327 (Count of Range Sum)?

This page provides optimized solutions for LeetCode problem 327 (Count of Range Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 327 (Count of Range Sum)?

The time complexity for LeetCode 327 (Count of Range Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 327 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 327 in Java, C++, or Python.

Back to LeetCode Solutions