# 862. Shortest Subarray with Sum at Least K

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int shortestSubarray(vector& nums, int k) { const int n = nums.size(); int ans = n + 1; deque q; vector prefix{0}; for (int i = 0; i < n; ++i) prefix.push_back(prefix.back() + nums[i]); for (int i = 0; i < n + 1; ++i) { while (!q.empty() && prefix[i] - prefix[q.front()] >= k) ans = min(ans, i - q.front()), q.pop_front(); while (!q.empty() && prefix[i] <= prefix[q.back()]) q.pop_back(); q.push_back(i); } return ans <= n ? ans : -1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int shortestSubarray(int[] nums, int k) { final int n = nums.length; int ans = n + 1; Deque q = new ArrayDeque<>(); long[] prefix = new long[n + 1]; for (int i = 0; i < n; ++i) prefix[i + 1] = (long) nums[i] + prefix[i]; for (int i = 0; i < n + 1; ++i) { while (!q.isEmpty() && prefix[i] - prefix[q.getFirst()] >= k) ans = Math.min(ans, i - q.pollFirst()); while (!q.isEmpty() && prefix[i] <= prefix[q.getLast()]) q.pollLast(); q.addLast(i); } return ans <= n ? ans : -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def shortestSubarray(self, nums: List[int], k: int) -> int: n = len(nums) ans = n + 1 q = collections.deque() prefix = [0] + list(itertools.accumulate(nums)) for i in range(n + 1): while q and prefix[i] - prefix[q[0]] >= k: ans = min(ans, i - q.popleft()) while q and prefix[i] <= prefix[q[-1]]: q.pop() q.append(i) return ans if ans <= n else -1