# LeetCode 862: Shortest Subarray with Sum at Least K

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to return the length of the shortest non-empty contiguous subarray whose sum is at least `k`.

If no such subarray exists, return `-1`.

A subarray must be contiguous. We cannot skip elements.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums`, an integer array |
| Input | `k`, the target minimum sum |
| Output | The length of the shortest non-empty subarray with sum at least `k` |
| Failure case | Return `-1` if no valid subarray exists |

Function shape:

```python
class Solution:
    def shortestSubarray(self, nums: list[int], k: int) -> int:
        ...
```

## Examples

Example 1:

```python
nums = [1]
k = 1
```

The subarray `[1]` has sum `1`, which is at least `1`.

So the answer is:

```python
1
```

Example 2:

```python
nums = [1, 2]
k = 4
```

The largest possible subarray sum is:

```python
1 + 2 = 3
```

That is less than `4`, so the answer is:

```python
-1
```

Example 3:

```python
nums = [2, -1, 2]
k = 3
```

The whole array has sum:

```python
2 + (-1) + 2 = 3
```

The length is `3`.

No shorter subarray reaches `3`, so the answer is:

```python
3
```

## First Thought: Sliding Window

For arrays with only positive numbers, we can use a normal sliding window.

We expand the right side until the sum is at least `k`, then shrink from the left while the sum stays valid.

That works when every number is positive because removing from the left always decreases the sum, and adding to the right always increases the sum.

Here, `nums` may contain negative numbers.

For example:

```python
nums = [2, -1, 2]
```

Adding a number can decrease the current sum, and removing a number can increase it. So a normal sliding window does not give a reliable rule.

We need prefix sums.

## Key Insight

Let `prefix[i]` be the sum of the first `i` numbers:

```python
prefix[0] = 0
prefix[i + 1] = prefix[i] + nums[i]
```

Then the sum of subarray `nums[left:right]` is:

```python
prefix[right] - prefix[left]
```

We need:

```python
prefix[right] - prefix[left] >= k
```

For each `right`, we want the best earlier `left`.

The shorter the subarray, the larger `left` should be. But the sum condition also depends on `prefix[left]`.

So we maintain a deque of candidate prefix indices.

The deque has two properties:

1. Indices are increasing.
2. Prefix sums are increasing.

Why keep prefix sums increasing?

If we have two candidate starts `i` and `j`, where:

```python
i < j
prefix[i] >= prefix[j]
```

then `i` is useless.

Starting at `j` is better because:

1. It is later, so it gives a shorter subarray.
2. Its prefix sum is smaller or equal, so it gives a larger or equal subarray sum.

Therefore, we can remove `i`.

## Algorithm

Build the prefix sum array.

Maintain a deque `dq` containing prefix indices.

For each prefix index `right`:

1. While the deque is not empty and:

```python
prefix[right] - prefix[dq[0]] >= k
```

we found a valid subarray.

Update the answer with:

```python
right - dq[0]
```

Then pop from the front, because that start index has now produced its shortest possible valid subarray.

2. While the deque is not empty and:

```python
prefix[right] <= prefix[dq[-1]]
```

pop from the back.

The old back index is dominated by `right`.

3. Append `right` to the deque.

At the end, return the best length if found. Otherwise return `-1`.

## Correctness

For any two prefix indices `left < right`, the subarray sum from `left` to `right - 1` is `prefix[right] - prefix[left]`.

So finding a subarray with sum at least `k` is equivalent to finding two prefix indices such that this difference is at least `k`.

The deque stores only useful starting indices. If a later prefix index has a smaller or equal prefix sum than an earlier one, the earlier one can never be better. The later index gives a shorter subarray and an equal or larger sum. Removing dominated indices is therefore safe.

When `prefix[right] - prefix[dq[0]] >= k`, the front of the deque forms a valid subarray ending at `right - 1`. Since `right` only increases, this is the shortest valid subarray that can ever be formed using that starting index. After updating the answer, popping it is safe.

The deque always preserves candidates that might still produce a shorter valid subarray later. Every valid optimal pair is considered before its start index is removed.

Therefore, the algorithm returns the length of the shortest non-empty subarray whose sum is at least `k`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each prefix index is added and removed at most once |
| Space | `O(n)` | The prefix array and deque may store up to `n + 1` indices |

## Implementation

```python
from collections import deque

class Solution:
    def shortestSubarray(self, nums: list[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        answer = n + 1
        dq = deque()

        for right in range(n + 1):
            while dq and prefix[right] - prefix[dq[0]] >= k:
                answer = min(answer, right - dq[0])
                dq.popleft()

            while dq and prefix[right] <= prefix[dq[-1]]:
                dq.pop()

            dq.append(right)

        return answer if answer <= n else -1
```

## Code Explanation

We first build prefix sums:

```python
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + nums[i]
```

This lets us compute any subarray sum in constant time.

The answer starts as an impossible length:

```python
answer = n + 1
```

The deque stores candidate starting indices:

```python
dq = deque()
```

For each possible ending prefix index:

```python
for right in range(n + 1):
```

we first check whether the oldest candidate can form a valid subarray:

```python
while dq and prefix[right] - prefix[dq[0]] >= k:
```

If it can, we update the shortest length:

```python
answer = min(answer, right - dq[0])
```

Then we remove that start index:

```python
dq.popleft()
```

Next, we remove dominated starts from the back:

```python
while dq and prefix[right] <= prefix[dq[-1]]:
    dq.pop()
```

If the current prefix sum is smaller or equal, the previous larger prefix sum is not useful as a future start.

Finally, we add the current index:

```python
dq.append(right)
```

If no answer was found, return `-1`:

```python
return answer if answer <= n else -1
```

## Testing

```python
def test_shortest_subarray():
    s = Solution()

    assert s.shortestSubarray([1], 1) == 1
    assert s.shortestSubarray([1, 2], 4) == -1
    assert s.shortestSubarray([2, -1, 2], 3) == 3
    assert s.shortestSubarray([1, 2, 3, 4], 6) == 2
    assert s.shortestSubarray([84, -37, 32, 40, 95], 167) == 3
    assert s.shortestSubarray([-28, 81, -20, 28, -29], 89) == 3

    print("all tests passed")

test_shortest_subarray()
```

Test meaning:

| Test | Why |
|---|---|
| `[1]`, `k = 1` | Minimum valid case |
| `[1, 2]`, `k = 4` | No valid subarray |
| `[2, -1, 2]`, `k = 3` | Negative number prevents simple sliding window |
| `[1, 2, 3, 4]`, `k = 6` | Positive-only case |
| `[84, -37, 32, 40, 95]`, `k = 167` | Valid subarray after negative value |
| `[-28, 81, -20, 28, -29]`, `k = 89` | Shortest valid subarray depends on prefix pruning |