@@ -0,0 +1,1394 @@
+# Time:  O(n)%0A# Space: O(n)%0A%0A# Return the length of the shortest, non-empty,%0A# contiguous subarray of A with sum at least K.%0A# If there is no non-empty subarray with sum at least K, return -1.%0A#%0A# Example 1:%0A#%0A# Input: A = %5B1%5D, K = 1%0A# Output: 1%0A# Example 2:%0A#%0A# Input: A = %5B1,2%5D, K = 4%0A# Output: -1%0A# Example 3:%0A#%0A# Input: A = %5B2,-1,2%5D, K = 3%0A# Output: 3%0A#%0A# Note:%0A# - 1 %3C= A.length %3C= 50000%0A# - -10 %5E 5 %3C= A%5Bi%5D %3C= 10 %5E 5%0A# - 1 %3C= K %3C= 10 %5E 9%0A%0Atry:%0A    xrange          # Python 2%0Aexcept NameError:%0A    xrange = range  # Python 3%0A%0Aimport collections%0A%0A%0Aclass Solution(object):%0A    def shortestSubarray(self, A, K):%0A        %22%22%22%0A        :type A: List%5Bint%5D%0A        :type K: int%0A        :rtype: int%0A        %22%22%22%0A        accumulated_sum = %5B0%5D*(len(A)+1)%0A        for i in xrange(len(A)):%0A            accumulated_sum%5Bi+1%5D = accumulated_sum%5Bi%5D+A%5Bi%5D%0A%0A        result = float(%22inf%22)%0A        mono_increasing_q = collections.deque()%0A        for i, curr in enumerate(accumulated_sum):%0A            while mono_increasing_q and curr %3C= %5C%0A                    accumulated_sum%5Bmono_increasing_q%5B-1%5D%5D:%0A                mono_increasing_q.pop()%0A            while mono_increasing_q and %5C%0A                    curr-accumulated_sum%5Bmono_increasing_q%5B0%5D%5D %3E= K:%0A                result = min(result, i-mono_increasing_q.popleft())%0A            mono_increasing_q.append(i)%0A        return result if result != float(%22inf%22) else -1%0A

Create shortest-subarray-with-sum-at-least-k.py