NeetCode #379LC-862HardStack
← Back to All Problems#379 · #862 · Shortest Subarray with Sum at Least K(和至少为 K 的最短子数组)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return the length of the shortest non-empty subarray with a sum of at least k. If no such subarray exists, return -1. Constraints: 1 <= nums.length <= 10^5, -10^5 <= nums[i] <= 10^5, 1 <= k <= 10^9.💡 Core Algorithmic Approaches
- Prefix sums are required, and because
numsmay contain negative values a plain sliding window does not apply. - Maintain a deque of indices with increasing prefix sums: it holds the candidates for the left end.
- For each right end
i, pop from the front whileprefix[i] - prefix[front] >= k, recording the length; those fronts are exhausted because a lateriwould give a longer subarray. - Then pop from the back any index whose prefix sum is at least
prefix[i], sinceidominates it as a left end.
💻 Benchmark Python3 Implementation
class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
from collections import deque
n = len(nums)
prefix = [0] * (n + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
dq = deque() # indices with increasing prefix sums
best = float("inf")
for i in range(n + 1):
# shrink from the front while the sum is large enough
while dq and prefix[i] - prefix[dq[0]] >= k:
best = min(best, i - dq.popleft())
# i dominates any earlier index with a >= prefix sum
while dq and prefix[dq[-1]] >= prefix[i]:
dq.pop()
dq.append(i)
return best if best != float("inf") else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index enters and leaves the deque at most once.
💾 Space Complexity
O(n) for the prefix array and the deque.
⚠️ Interview Pitfalls & Follow-ups
- Using a sliding window: it fails with negative values, since the sum is not monotone in the window bounds.
- Popping from the front without recording the length first: the length must be captured before the pop.
- Omitting the back-popping step: the deque would no longer be increasing in prefix sum and the front would not be the best candidate.
- Forgetting the
-1case: no subarray may reach the required sum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.