N*log(N) Python solution based on Right-most Insertion Point (RMIP)


  • 0
    class Solution(object):
    
        # O(NlogN) O(N) solution based on right-most insertion point
    
        def minSubArrayLen(self, s, nums):
    
            def bs(a, k, beg, end):
                while beg <= end:
                    mid = (beg + end) >> 1
                    if a[mid] > k:
                        end = mid - 1
                    else:
                        beg = mid + 1
                return beg
    
            n = len(nums)
            if not n:
                return 0
            run = 0
            sums = [0] * (n + 1)
            for i in range(n):
                run += nums[i]
                sums[i + 1] = run
            i, min_int = n, sys.maxsize
            while i > 0 and sums[i] >= s:
                idx = bs(sums, sums[i] - s, 0, i)
                idx = idx - 1
                if idx >= 0:
                    min_int = min(min_int, i - idx)
                i -= 1
            return 0 if min_int == sys.maxsize else min_int

Log in to reply
 

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