DevExCode

LeetCode 327: Count of Range Sum

ArrayBinary SearchDivide and ConquerBinary Indexed TreeSegment TreeMerge SortOrdered Set

LeetCode 327 Solution 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.

View LeetCode 327 on LeetCode

LeetCode 327 Solutions in Java, C++, Python

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

Interactive Code Editor for LeetCode 327

Improve Your LeetCode 327 Solution

Use the editor below to refine the provided solution for LeetCode 327. Select a programming language and try the following:

  • Add import statements if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Loading editor...

Related LeetCode Problems

Previous LeetCode ProblemNext LeetCode Problem