862. Shortest Subarray with Sum at Least K

class Solution:
    def shortestSubarray(self, A: List[int], k: int) -> int:
        """ tc O(N) sc O(N)
        main idea:  mono queue  (increasing)
        1. initialize queue with [0,-1] 
        2. if psum - queue[0] >= k,  update result 
        3. before insert current psum with index in the queue, remove elements from the tail that smaller than current psum 
        """
        res = float('inf')
        psum = 0 
        q = collections.deque()
        q.append([0,-1])# psumL, idx 
        for i, a in enumerate(A):
            psum += a
            while q and psum - q[0][0]  >= k:
                res = min(res, i - q.popleft()[1])
            
            while q and q[-1][0] >= psum:
                q.pop()
            q.append([psum, i])
        return res   if res < float('inf') else -1