862. Shortest Subarray with Sum at Least K

Problem Link

Description

---

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

 

Constraints:

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

Solution

---

Python3

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        N = len(nums)
        queue = deque([(0, 0)])
        res = inf
        s = 0
 
        for j, x in enumerate(nums):
            s += x
 
            while queue and s - queue[0][1] >= k:
                i, _ = queue.popleft()
                res = min(res, j - i + 1)
            
            while queue and queue[-1][1] >= s:
                queue.pop()
 
            queue.append((j + 1, s))
       
        
        return -1 if res == inf else res