No BST, no BIT, O(nlogn) binary search Python solution that beats 99%


  • 0
    C

    Inspired by two following questions:

    1. max subarray no larger than K
    2. max rectangle area no larger than K

    Small changes I made in the code: instead of finding the max, I found the indices of low and high, and then add up the index diff to count.

    def countRangeSum(self, nums, lower, upper):
            """
            :type nums: List[int]
            :type lower: int
            :type upper: int
            :rtype: int
            """
            slist, cur_sum, count = [], 0, 0
            for num in nums:
                cur_sum += num
                if lower <=cur_sum <= upper:
                    count += 1
                if not slist:
                    slist.append(cur_sum)
                    continue
                low = cur_sum - lower
                hi = cur_sum - upper
                idx_lo = bisect.bisect_right(slist, low)
                idx_hi = bisect.bisect_left(slist, hi)
                count += abs(idx_lo - idx_hi)
                bisect.insort(slist, cur_sum)
            return count
    

  • 0

    Wouldn't the bisect.insort() run inO(n)?


Log in to reply
 

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