Shortest Subarray with Sum at Least K - Solution & Explanation

Problem Overview: You are given an integer array nums and an integer k. The goal is to find the length of the shortest non‑empty subarray whose sum is at least k. The challenge comes from negative numbers in the array, which break the standard sliding window strategy used for positive-only arrays.

Approach 1: Brute Force Subarray Check (O(n²) time, O(1) space)

The most direct strategy is to examine every possible subarray. Start from each index i, keep a running sum while extending the subarray to the right, and stop once the sum becomes at least k. Track the minimum length encountered. This works because every subarray is evaluated explicitly, but the nested iteration leads to O(n²) time in the worst case. It is useful as a baseline to verify correctness and understand the structure of the problem, but it does not scale when n is large.

Approach 2: Prefix Sum + Monotonic Deque (O(n) time, O(n) space)

The optimal approach uses prefix sums and a monotonic queue. First compute a prefix array where prefix[i] stores the sum of the first i elements. Any subarray sum from i to j can then be computed as prefix[j] - prefix[i]. The goal becomes finding indices i < j where this difference is at least k while minimizing j - i.

A deque stores candidate prefix indices in increasing order of their prefix values. While iterating through the prefix array, two checks keep the structure optimal. First, if the difference between the current prefix and the front of the deque is at least k, you found a valid subarray and update the minimum length while popping from the front. Second, maintain monotonicity: if the current prefix value is smaller than the last stored prefix, remove the larger one because it will never produce a better result later. Each index enters and leaves the deque at most once, which keeps the total runtime linear.

This technique handles negative numbers gracefully and avoids the pitfalls of a standard sliding window. The combination of prefix sums and a monotonic structure ensures that only useful candidates remain in the deque during iteration.

Recommended for interviews: The prefix sum with monotonic deque solution is what interviewers expect for this problem. It demonstrates understanding of prefix transformations and efficient candidate pruning using a deque. Mentioning the brute force approach first shows you understand the search space, but implementing the O(n) solution signals strong algorithmic maturity.