Description

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [1], K = 1 Output: 1 Example 2:

Input: A = [1,2], K = 4 Output: -1 Example 3:

Input: A = [2,-1,2], K = 3 Output: 3

Note:

1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9

Solution

If we precompute the accumulate sum of the array as accs. Then we need to find two element in accs whose difference is at least K and as close as possible. We can utlize a monotonically increasing deque to accomplish that.

When we iterate over accs and saw a new element, if its value is smaller than the end of the queue, we can safetly pop the end of the queue out, because any later element will have larger difference with current element and smaller length. Therefore, the queue will be monotically increasing.

So we can calculate the difference between current element and the front of the queue. If the diff is at least K, we can get the length and compare with the current smallest length. We can do this and pop out the front of the queue until the difference is no longer at least K.

We can do this, because any element later than current element will be larger and its difference with the already popped out element from the front of the queue will be longer in length.

Below is the implementation

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        '''
        0, 2, 1, 3
        stack = []
        [a] b if a > b, then we can pop a out and push b to the queue because any element x after b x - b > x - a with x - b array length shorter than x - a. So we can safely pop out a
        if left of the queue has value c and b - c >= K, then we can calculate the length and pop out c safely, since if d which is later than b and d > b, then d - c >= K and the length is larger than b - c. So we can safetly pop out c.
        '''
        n = len(A)
        accs = [0]
        acc = 0
        for num in A:
            acc += num
            accs.append(acc)
        queue = collections.deque()
        queue.append((0,0))
        ret = float('inf')
        for i in range(1,n + 1):
            while len(queue) and accs[i] < queue[-1][0]:
                queue.pop()
            while len(queue) and accs[i] - queue[0][0] >= K:
                ret = min(ret, i - queue[0][1])
                queue.popleft()
            queue.append((accs[i], i))
        return ret if ret < float('inf') else -1

Time complexity is O(n)