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

Function shape:

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

Examples

Example 1:

nums = [1]
k = 1

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

So the answer is:

1

Example 2:

nums = [1, 2]
k = 4

The largest possible subarray sum is:

1 + 2 = 3

That is less than 4, so the answer is:

-1

Example 3:

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

The whole array has sum:

2 + (-1) + 2 = 3

The length is 3.

No shorter subarray reaches 3, so the answer is:

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:

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:

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

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

prefix[right] - prefix[left]

We need:

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:

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:

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

we found a valid subarray.

Update the answer with:

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:

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

Implementation

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:

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:

answer = n + 1

The deque stores candidate starting indices:

dq = deque()

For each possible ending prefix index:

for right in range(n + 1):

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

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

If it can, we update the shortest length:

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

Then we remove that start index:

dq.popleft()

Next, we remove dominated starts from the back:

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:

dq.append(right)

If no answer was found, return -1:

return answer if answer <= n else -1

Testing

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: