# Shortest Subarray with Sum at Least K
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k)
Canonical: https://scaleengineer.com/dsa/problems/shortest-subarray-with-sum-at-least-k
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Heap (Priority Queue), Queue, Monotonic Queue
---
## Problem
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.

**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 <= 105`
* `-105 <= nums[i] <= 105`
* `1 <= k <= 109`

# Approaches
## Prefix Sum with Brute Force
A straightforward but inefficient approach involves pre-calculating prefix sums to quickly find the sum of any subarray. We then iterate through all possible start and end points of a subarray, check if its sum is at least `k`, and keep track of the minimum length found.
**Time:** O(n^2), where n is the number of elements in `nums`. The prefix sum calculation takes O(n), but the nested loops to check every subarray dominate the runtime. · **Space:** O(n) to store the prefix sum array.
**Pros:** More efficient than a naive O(n^3) brute-force approach.; Relatively easy to understand the logic based on prefix sums.
**Cons:** The O(n^2) time complexity is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error.
### Explanation
This method improves upon a naive brute-force solution by optimizing the sum calculation for each subarray. 

1.  **Prefix Sum Calculation:** First, we create a prefix sum array, `prefix`, of size `n + 1`, where `n` is the length of `nums`. `prefix[i]` stores the sum of elements from `nums[0]` to `nums[i-1]`. `prefix[0]` is initialized to 0. This allows us to calculate the sum of any subarray `nums[i...j]` in constant time using the formula `prefix[j+1] - prefix[i]`. This pre-computation step takes O(n) time.

2.  **Iterating Subarrays:** After computing the prefix sums, we use two nested loops to examine every possible non-empty subarray. The outer loop selects a starting index `i` from `0` to `n-1`, and the inner loop selects an ending index `j` from `i` to `n-1`.

3.  **Checking Condition:** For each subarray defined by `(i, j)`, we calculate its sum `prefix[j+1] - prefix[i]`. If this sum is greater than or equal to `k`, we have found a valid subarray. We then update our minimum length found so far with `min(minLength, j - i + 1)`.

4.  **Result:** We initialize `minLength` to a value larger than `n` (e.g., `n + 1`). If `minLength` remains this value after checking all subarrays, it means no solution exists, and we return -1. Otherwise, we return the final `minLength`.

```java
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int minLength = n + 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                long sum = prefix[j + 1] - prefix[i];
                if (sum >= k) {
                    minLength = Math.min(minLength, j - i + 1);
                }
            }
        }

        return minLength == n + 1 ? -1 : minLength;
    }
}
```
### Algorithm
1. Create a prefix sum array `prefix` of size `n + 1`. Use `long` to prevent integer overflow, as sums can be large.
2. Populate the `prefix` array: `prefix[i+1] = prefix[i] + nums[i]` for `i` from `0` to `n-1`.
3. Initialize `minLength = n + 1` to store the result.
4. Iterate with a start index `i` from `0` to `n-1`.
5. Inside this loop, iterate with an end index `j` from `i` to `n-1`.
6. Calculate the subarray sum: `sum = prefix[j+1] - prefix[i]`.
7. If `sum >= k`, update `minLength = Math.min(minLength, j - i + 1)`.
8. After the loops, if `minLength` is still `n + 1`, return `-1`. Otherwise, return `minLength`.

## Sliding Window with Monotonic Deque
The optimal solution uses prefix sums combined with a sliding window managed by a monotonic deque. This approach achieves linear time complexity by efficiently finding the shortest valid subarray ending at each position. The deque helps maintain potential starting points for subarrays in a way that handles the complication of negative numbers.
**Time:** O(n), where n is the length of `nums`. Each index is added to and removed from the deque at most once. The entire process is a single pass over the prefix sum array. · **Space:** O(n) for storing the prefix sum array and the deque. In the worst-case scenario, the deque could potentially store all `n+1` indices.
**Pros:** Optimal O(n) time complexity, making it very efficient for large inputs.; Correctly handles arrays with negative numbers, which is a key challenge in this problem.
**Cons:** The logic is more complex and less intuitive than the brute-force approach.; Requires careful implementation to handle the deque operations and edge cases correctly.
### Explanation
This advanced approach leverages prefix sums to reframe the problem and a deque to maintain candidate indices efficiently.

The problem is to find the smallest `y - x` such that `sum(nums[x...y-1]) >= k`. Using prefix sums `P`, this is equivalent to finding the smallest `y - x` such that `P[y] - P[x] >= k`.

For a fixed endpoint `y`, we want to find an `x < y` that satisfies `P[x] <= P[y] - k` and is as large as possible (to minimize `y - x`).

We can process the prefix sums `P` from left to right (indexed by `y`). We use a deque to store indices `x` of promising starting points. The deque will store indices `d_1, d_2, ...` such that their corresponding prefix sums are strictly increasing: `P[d_1] < P[d_2] < ...`.

**Algorithm Steps:**
1.  **Prefix Sums:** Compute the prefix sum array `P` of size `n+1`. Use `long` to avoid overflow.
2.  **Initialization:** Create an empty deque `dq` to store indices and initialize `minLength = n + 1`.
3.  **Iteration:** Iterate through the prefix sum array with index `y` from `0` to `n`.
    a.  **Condition Check (Shrinking Window from Left):** Look at the index at the front of the deque, `x = dq.peekFirst()`. If `P[y] - P[x] >= k`, we've found a valid subarray of length `y - x`. We update `minLength` and then remove `x` from the deque (`dq.pollFirst()`). We remove it because for any future endpoint `y' > y`, a subarray starting at `x` would be longer than `y' - x'`, where `x'` is another valid start. We've found the shortest possible subarray starting at `x`, so it's no longer needed.
    b.  **Monotonicity Maintenance (Optimizing Candidates):** Look at the index at the back of the deque, `x_last = dq.peekLast()`. If `P[y] <= P[x_last]`, we remove `x_last` from the deque (`dq.pollLast()`). The reason is that `y` is a better future candidate for a starting index than `x_last`. If we have `x_last < y` and `P[x_last] >= P[y]`, then for any future endpoint `z > y`, if `P[z] - P[x_last] >= k`, it must be that `P[z] - P[y] >= k` as well. The subarray starting at `y` (`z-y`) would be shorter than the one starting at `x_last` (`z-x_last`). So, `x_last` becomes redundant.
    c.  **Add to Window:** Add the current index `y` to the back of the deque.

After iterating through all `y`, if `minLength` is still `n + 1`, no such subarray exists. Otherwise, `minLength` holds the answer.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int minLength = n + 1;
        Deque<Integer> dq = new ArrayDeque<>();

        for (int y = 0; y <= n; y++) {
            // Condition: prefix[y] - prefix[x] >= k
            while (!dq.isEmpty() && prefix[y] - prefix[dq.peekFirst()] >= k) {
                minLength = Math.min(minLength, y - dq.pollFirst());
            }

            // Maintain monotonic deque: prefix[d1] < prefix[d2] < ...
            while (!dq.isEmpty() && prefix[y] <= prefix[dq.peekLast()]) {
                dq.pollLast();
            }

            dq.addLast(y);
        }

        return minLength == n + 1 ? -1 : minLength;
    }
}
```
### Algorithm
1. Create a `long` prefix sum array `prefix` of size `n + 1` and populate it.
2. Initialize `minLength = n + 1` and an empty `Deque<Integer> dq`.
3. Iterate with index `y` from `0` to `n` (representing the end of the subarray).
4. **Check for valid subarrays:** While the deque is not empty and `prefix[y] - prefix[dq.peekFirst()] >= k`, update `minLength = min(minLength, y - dq.pollFirst())` and remove the first element from the deque.
5. **Maintain deque monotonicity:** While the deque is not empty and `prefix[y] <= prefix[dq.peekLast()]`, remove the last element from the deque.
6. Add the current index `y` to the end of the deque.
7. After the loop, if `minLength > n`, return `-1`. Otherwise, return `minLength`.

# Solutions
### Java

```java
class Solution {
public
  int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] s = new long[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    Deque<Integer> q = new ArrayDeque<>();
    int ans = n + 1;
    for (int i = 0; i <= n; ++i) {
      while (!q.isEmpty() && s[i] - s[q.peek()] >= k) {
        ans = Math.min(ans, i - q.poll());
      }
      while (!q.isEmpty() && s[q.peekLast()] >= s[i]) {
        q.pollLast();
      }
      q.offer(i);
    }
    return ans > n ? -1 : ans;
  }
}

```

### JavaScript

```javascript
function shortestSubarray ( nums , k ) { const [ n , MAX ] = [ nums . length , Number . POSITIVE_INFINITY ]; const s = Array ( n + 1 ). fill ( 0 ); const q = []; let ans = MAX ; for ( let i = 0 ; i < n ; i ++ ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } for ( let i = 0 ; i < n + 1 ; i ++ ) { while ( q . length && s [ i ] - s [ q [ 0 ]] >= k ) { ans = Math . min ( ans , i - q . shift ()); } while ( q . length && s [ i ] <= s [ q . at ( - 1 )]) { q . pop (); } q . push ( i ); } return ans === MAX ? - 1 : ans ; }
```

### CPP

```cpp
class Solution {
public:
  int shortestSubarray(vector<int> &nums, int k) {
    int n = nums.size();
    vector<long> s(n + 1);
    for (int i = 0; i < n; ++i)
      s[i + 1] = s[i] + nums[i];
    deque<int> q;
    int ans = n + 1;
    for (int i = 0; i <= n; ++i) {
      while (!q.empty() && s[i] - s[q.front()] >= k) {
        ans = min(ans, i - q.front());
        q.pop_front();
      }
      while (!q.empty() && s[q.back()] >= s[i])
        q.pop_back();
      q.push_back(i);
    }
    return ans > n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int: s = list(accumulate(nums, initial=0)) q = deque() ans = inf for i, v in enumerate(s): while q and v - s[q[0]] >= k: ans = min(ans, i - q . popleft()) while q and s[q[- 1]] >= v: q . pop() q . append(i) return - 1 if ans == inf else ans

```