DevExCode

LeetCode 327: Count of Range Sum

ArrayBinary SearchDivide and ConquerBinary Indexed TreeSegment TreeMerge SortOrdered Set

Problem Description

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.

View on LeetCode

Solutions

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;
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...