⚡Flashcard Drill➔
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

  1. Prefix sums are required, and because nums may contain negative values a plain sliding window does not apply.
  2. Maintain a deque of indices with increasing prefix sums: it holds the candidates for the left end.
  3. For each right end i, pop from the front while prefix[i] - prefix[front] >= k, recording the length; those fronts are exhausted because a later i would give a longer subarray.
  4. Then pop from the back any index whose prefix sum is at least prefix[i], since i dominates 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 -1 case: 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems