Java Using Binary Search nlog(n)


  • 0
    F

    Just want to give another way to solve this problem in nlgn time. So here is the basic idea: First we calculate the presum. The for two elements i and j, 0 <= i < j ---i------j----- we have the relation: lower <= prev[j] - prev[i-1] <= upper. So if we fix j, then it becomes lower + prev[i-1] <= prev[j] <= upper + prev[i-1]. This problem becomes a range search problem. We iterate the presum array from the beginning to the end and keep it sorted. For each search and insert will take lgn time, and we will do this operation for n times. Hence the total running time will be nlgn

    public class Solution {
       public int countRangeSum(int[] nums, int lower, int upper) {
            int res = 0;
            long[] prev = new long[nums.length + 1];
            for (int i = 1; i <= nums.length; ++i)
                prev[i] = prev[i-1] + nums[i-1];
    
            ArrayList<Long> sorted = new ArrayList();
            sorted.add((long)0);
            for (int i = 1; i < prev.length; ++i) {
                // find lower bound using binary search
                int lb = bsLower(sorted,  prev[i] - upper);
                //find upper bound using binary search
                int ub = bsUpper(sorted, prev[i] - lower);
                res += ub - lb;
                //find the insertion place
                int index = bsLower(sorted, prev[i]);
                sorted.add(index, prev[i]);
            }
            return res;
        }
        private int bsLower(ArrayList<Long> sorted, long target) {
            int start = 0, end = sorted.size()-1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (sorted.get(mid) >= target) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            if (start <= end && sorted.get(start) >= target) {
                return start;
            }
            if (start < end && sorted.get(end) >= target) {
                return end;
            }
            return end + 1;
        }
        private int bsUpper(ArrayList<Long> sorted, long target) {
            int start = 0, end = sorted.size()-1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (sorted.get(mid) <= target) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            if (start <= end && sorted.get(start) > target) {
                return start;
            }
            if (start < end && sorted.get(end) > target) {
                return end;
            }
            return end + 1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.