[Python] Very short and simple binary search, 99.5%+

  • 0

    As discussed in other solutions, we want to find all P[j] with j > i (Condition 1) and P[i]+lower <= P[j] <= P[i]+upper (Condition 2), where P[x] = sum(A[:x]).

    Put P[N-1], P[N-2], ...P[0] etc. in sorted order into B. When we put a P[i] into B, B only contained P[j]'s with j > i, which takes care of the first condition. We use binary search to find the number of P[j]'s in the valid range for the second condition.

    class Solution(object):
        def countRangeSum(self, A, lower, upper):
            su = sum(A)
            B = [su]
            ans = 0
            for x in A[::-1]:
                su -= x
                ix = bisect.bisect_left(B, lower+su)
                jx = bisect.bisect_right(B, upper+su)
                ans += max(0, jx-ix)
                bisect.insort(B, su)
            return ans

    Keep in mind bisect.insort has the list insertion which is O(N), but in practice this is fast.

Log in to reply

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