Leetcode 892 Solution

This article provides solution to leetcode question 892 (shortest-subarray-with-sum-at-least-k)
Categories:
Tags:
Access this page by simply typing in "lcs 892" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k

Solution

class Solution(object):
    def shortestSubarray(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        S = [0]
        for a in A:
            S.append(a + S[-1])

        q = collections.deque()

        ans = len(A) + 1
        for i, s in enumerate(S):
            while q and S[q[-1]] >= s:
                q.pop()

            while q and s - S[q[0]] >= K:
                ans = min(i - q[0], ans)
                q.popleft()

            q.append(i)

        return ans if ans <= len(A) else -1