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.

Examples

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 <= 10^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= 10^9

Thinking Process

  1. Negative Numbers Break Simple Sliding Window: Cannot shrink window from left when sum >= k
    • If preSum[i] <= preSum[j] and i < j, then i is always better
    • Remove from front: processed starting positions
    • Remove from back: maintain monotonic property
  • Maintain a window [left, right] satisfying a constraint.
  • Expand right to grow; shrink left when invalid.
  • Fixed window: slide both pointers together.
Sliding window a b c d e window expand right, shrink left when invalid

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Solution

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        if(nums.empty()) return -1;
        const int N = nums.size();
        vector<long> preSum(N + 1);
        for(int i = 0; i < N; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int rtn = INT_MAX;
        deque<int> q;
        for(int i = 0; i <= N; i++) {
            long curSum = preSum[i];
            while(!q.empty() && curSum - preSum[q.front()] >= k) {
                rtn = min(rtn, i - q.front());
                q.pop_front();
            }
            while(!q.empty() && preSum[q.back()] >= curSum) {
                q.pop_back();
            }
            q.push_back(i);
        }
        return rtn == INT_MAX? -1: rtn;
    }
};

Solution Explanation

Approach: Fixed-size window (this problem)

Key idea: 1. Negative Numbers Break Simple Sliding Window: Cannot shrink window from left when sum >= k

How the code works:

  1. Negative Numbers Break Simple Sliding Window: Cannot shrink window from left when sum >= k
    • If preSum[i] <= preSum[j] and i < j, then i is always better
    • Remove from front: processed starting positions
    • Remove from back: maintain monotonic property
    • Maintain a window [left, right] satisfying a constraint.
    • Expand right to grow; shrink left when invalid.

Walkthrough — input nums = [1], k = 1, expected output 1:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  4. Empty array: nums = [] → return -1
  5. No valid subarray: nums = [1,2], k = 4 → return -1
  6. Single element: nums = [1], k = 1 → return 1
  7. Negative numbers: nums = [2,-1,2], k = 3 → return 3
  8. All negative: nums = [-1,-2,-3], k = 1 → return -1

  9. Large k: nums = [1,2], k = 10^9 → return -1

  10. Using simple sliding window: Fails with negative numbers
  11. Not maintaining monotonic property: Leads to incorrect results
  12. Wrong deque operations: Removing from wrong end
  13. Integer overflow: Not using long for prefix sums
  14. Index confusion: Mixing 0-indexed and 1-indexed arrays
  15. Not checking empty deque: Accessing q.front() or q.back() without checking

Comparison with LC 209

Aspect LC 209 (All Positive) LC 862 (Can Have Negatives)
Approach Simple sliding window Monotonic deque
Time O(n) O(n)
Space O(1) O(n)
Complexity Simpler More complex
Key Insight Shrink window when sum >= k Maintain monotonic deque

Key Takeaways

  1. Negative Numbers Break Simple Sliding Window: Cannot shrink window from left when sum >= k

  2. Prefix Sum Enables Range Queries: preSum[j+1] - preSum[i] = sum from i to j

  3. Monotonic Deque: Maintains indices with increasing prefix sums
    • If preSum[i] <= preSum[j] and i < j, then i is always better
  4. Why Deque?: Need O(1) operations on both ends
    • Remove from front: processed starting positions
    • Remove from back: maintain monotonic property
  5. Two While Loops:
    • First loop: find valid subarrays ending at current position
    • Second loop: maintain monotonic property for future positions

References

Template Reference