327. Count of Range Sum (1)

Link

Given an integer array nums, 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 (i ≤ j), inclusive.

Note: A naive algorithm of O(n^2) is trivial. You MUST do better than that.

Example:

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

Solution

For leetcode 327, applying the sequential recurrence relation (with j fixed) on the pre-sum array, the subproblem C reads: find the number of elements out of visited ones that are within the given range, which again involves searching on "dynamic searching space"; applying the partition recurrence relation, we have a subproblem C: for each element in the left half, find the number of elements in the right half that are within the given range, which can be embedded into the merging process using the two-pointer technique.

1. 先將從頭到任何位置的區間sum值放到一個n+1大小的array : sum，其中sum[i] 表示 nums[0] + nums[1] + ... + num[i-1] 的值，其中num[i] is exclusive

2. 那麼區間[i, j-1]的sum值 S(i,j-1)就可以理解成 sum[j] - sum[i]，問題就簡化成要求得有多少的S(i, j-1) 符合規則

3. 找尋範圍的方法可透過mergeSort，merge時左右兩邊的已經sort過。針對左邊的每個index i，尋找右邊是否有某個區間(k, j) 使得 S(i, k) ~ S(i, j)都能符合規則，那這時j-k就是針對index i所有可能的區間數

• j is the first index satisfy sums[j] - sums[i] > upper and

• k is the first index satisfy sums[k] - sums[i] >= lower.

Then the number of sums in [lower, upper] is j-k. We also use another index t to copy the elements satisfy sums[t] < sums[i] to a cache in order to complete the merge sort.

Despite the nested loops, the time complexity of the "merge & count" stage is still linear. Because the indices k, j, t will only increase but not decrease, each of them will only traversal the right half once at most. The total time complexity of this divide and conquer solution is then O(n log n).

One other concern is that the sums may overflow integer. So we use long instead.

Java - Merge Sort Solution

 public int countRangeSum(int[] nums, int lower, int upper) {
        int len = nums.length;
        long[] sum = new long[len + 1];
        
        for(int i = 0; i < len ; i++){
            sum[i+1] = sum[i] + nums[i];
        }
        return mergeSortAndCount(sum, 0, len+1, lower, upper);
    }
    
    
    public int mergeSortAndCount(long[] sum, int start, int end, int lower, int upper){
        if(end - start <= 1) return 0; //remember: merge sort到只剩兩個元素就不用merge了
        int mid = (start + end)/2;
        int count = mergeSortAndCount(sum, start, mid, lower, upper) + mergeSortAndCount(sum, mid, end, lower, upper);
        
        int k = mid, j = mid, t = mid;
        long[] cache = new long[end - start]; //為何是end - start 而非 end -start + 1
        for(int i = start, r = 0; i < mid; i++, r++){ 
            while( k < end && sum[k] - sum[i] < lower) k++;
            while( j < end && sum[j] - sum[i] <= upper) j++;
            //把sort結果存到新的cache array
            while( t < end && sum[t] < sum[i]) cache[r++] = sum[t++];
            cache[r] = sum[i];
            count += j-k;
        }
        System.arraycopy(cache, 0, sum, start, t-start); // 為何是t-start 而非end -start
        return count;
    }