@@ -0,0 +1,1745 @@
+package com.interview.misc;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0Aimport java.util.NavigableMap;%0Aimport java.util.TreeMap;%0A%0A/**%0A * Date 03/03/2016%0A * @author Tushar Roy%0A *%0A * Given an integer array nums, return the number of range sums that lie in %5Blower, upper%5D inclusive.%0A *%0A * Time complexity O(nlogn)%0A * Space complexity O(n)%0A *%0A * Performance can be improved by using self balancing BST which keeps the count of key and size of substree under it%0A *%0A * https://leetcode.com/problems/count-of-range-sum/%0A */%0Apublic class CountRanges %7B%0A%0A    public int countRangeSum(int%5B%5D nums, int lower, int upper) %7B%0A        TreeMap%3CLong, Integer%3E map = new TreeMap%3C%3E();%0A        Map%3CLong, Integer%3E countMap = new HashMap%3C%3E();%0A        long prefixSum%5B%5D = new long%5Bnums.length + 1%5D;%0A        map.put(0l, 1);%0A        countMap.put(0l, 1);%0A        int count = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            prefixSum%5Bi+1%5D = prefixSum%5Bi%5D + nums%5Bi%5D;%0A            NavigableMap%3CLong, Integer%3E rangeMap =  map.subMap(prefixSum%5Bi+1%5D - upper, true, prefixSum%5Bi+1%5D - lower, true);%0A            if (rangeMap.size() %3E 0) %7B%0A                for (int c : rangeMap.values()) %7B%0A                    count += c;%0A                %7D%0A            %7D%0A            if (countMap.containsKey(prefixSum%5Bi+1%5D)) %7B%0A                countMap.put(prefixSum%5Bi+1%5D, countMap.get(prefixSum%5Bi+1%5D) + 1);%0A            %7D else %7B%0A                countMap.put(prefixSum%5Bi+1%5D, 1);%0A            %7D%0A%0A            map.put(prefixSum%5Bi+1%5D, countMap.get(prefixSum%5Bi+1%5D));%0A        %7D%0A        return count;%0A    %7D%0A%0A    public static void main(String args%5B%5D) %7B%0A        CountRanges cr = new CountRanges();%0A        int%5B%5D input = %7B0, 0%7D;%0A        System.out.print(cr.countRangeSum(input, 0, 0));%0A    %7D%0A%0A%7D%0A%0A

count ranges which fall under given range