Problem statement

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

Solution

Quite difficult problem for me, I think I need to digest it and go back after some time. Let us evaluate cumulative sums B. Then for each element we need to answer question: Given B[i], the problem is equivalent to finding the nearest previous element B[l] such that B[l] <= B[i] - K. Let us keep deque of indexes i1 < ... ik, such that B_{i1} < ... < B_{ik}. It will keep the possible values of the start of our subarray.

  1. Let us consider element i: we need to find nearest previous elements l, such that B[i] - K >= B[l].
  2. If it happens, that for first element of our deque this condition is true, then it means that we already find shortest subarray which started with index in the beginning of deque, and we can pop it. We continue to pop until we can.
  3. Also, if new element is less or equal than last element of deque, we pop last element: in this way we keep increasing deque.

Complexity

Time and space complexity is O(n).

Code

#### borrowed code
class Solution:
    def shortestSubarray(self, A, K):
        n = len(A)
        B = [0] + list(accumulate(A))
        d = deque()
        res = n + 1
        for i in range(n + 1):
            while d and B[i] - K >= B[d[0]]: res = min(res, i - d.popleft())
            while d and B[i] <= B[d[-1]]: d.pop()
            d.append(i)
        return res if res <= n else -1

Remark

In general monotonic deque will have the following pattern: A[i] = min(A[j:k]) + C where j < k <= i