Leetcode Count of Range Sum problem solution

YASH PAL,

In this Leetcode Count of Range Sum problem solution You are 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.

Leetcode Count of Range Sum problem solution

Problem solution in Python.

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        res = 0
        presum = 0
        sorted_presum = [0]
        for k in range(len(nums)):
            presum += nums[k]
            idx_c = bisect_right(sorted_presum, presum)
            idx_l = bisect_left(sorted_presum, presum - upper)
            idx_r = bisect_right(sorted_presum, presum - lower)
            res += idx_r - idx_l

            sorted_presum[idx_c:idx_c] = [presum]
            
        return res

Problem solution in Java.

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        
        return countRanges(nums, lower, upper);
    }
    
    private int countRanges(int[] nums, int lower, int upper) {
        long sum = 0;
        Map<Long, Integer> sumMap = new HashMap<>();
        int count = 0;
        sumMap.put(0l, 1);
        for(int i=0; i<nums.length; i++) {
            sum = sum + nums[i];
            
            for(int j=lower; j<=upper; j++) {
                Integer prev = sumMap.get(sum-j);
                if(prev != null) {
                    count = count + prev;
                }
            }
            
            if(!sumMap.containsKey(sum)) {
                sumMap.put(sum, 0);
            }
            sumMap.put(sum, sumMap.get(sum) + 1);
        }
        
        return count;
    }
}

Problem solution in C++.

int countRangeSum(vector<int>& A, int lower, int upper) {
        int n = A.size();
        vector<long> prefix(n + 1), aux(n + 1);
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + A[i];
        return countRangeSum(prefix, 0, n + 1, lower, upper, aux);
}

int countRangeSum(vector<long> &prefix, int beg, int end, int lower, int upper, vector<long> &aux) {
    if (end - beg <= 1) return 0;
    auto mid = beg + (end - beg) / 2;
    auto count = countRangeSum(prefix, beg, mid, lower, upper, aux) 
               + countRangeSum(prefix, mid, end, lower, upper, aux);
    auto p = beg;
    for (int i = beg, j = mid, k = mid, t = mid; i < mid; ++i) {
        while (j < end && prefix[j] - prefix[i] <  lower) ++j;
        while (k < end && prefix[k] - prefix[i] <= upper) ++k;
        while (t < end && prefix[t] < prefix[i]) aux[p++] = prefix[t++];
        aux[p++] = prefix[i];
        count += k - j;
    }
    while (beg < p) prefix[beg] = aux[beg++];
    return count;
}

Problem solution in C.

int countConsistentStrings(char * allowed, char ** words, int wordsSize){
int freq[26] = {0};
  int j;
    int count = wordsSize;
    for(int i = 0; i < strlen(allowed); i++){
        freq[allowed[i] - 97]++;
    }

 
    for(int i = 0; i < wordsSize; i++){
        for(j = 0; j < strlen(words[i]); j++){
           if(freq[*(words[i]+ j) -97] == 0){ 
               count = count - 1;
               break;
           }
        } 
    }
    return count;
}

coding problems