Problem statement

https://binarysearch.com/problems/Smallest-Sublist-Sum-at-Least-Target/

Solution 1

Equal to Leetcode 0862 Shortest Subarray with Sum at Least K.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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

Solution 2

Alternative way is to use heaps, we will keep pairs (prefix sum, index) in heap. Also we delete elements from heap if we have sum >= K, for this indexes we can be sure that we look for the shortest window: after this end can only be increased.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def shortestSubarray(self, A, K):
        pq, sm, ans = [(0, -1)], 0, float("inf")
        for i, n in enumerate(A):
            sm += n
            while pq and sm - K >= pq[0][0]:
                ans = min(ans, i - heappop(pq)[1])
            heapq.heappush(pq, (sm, i))
            
        return ans if ans < float("inf") else -1