Shortest Run Summing to at Least K
Problem
Given a list of integers nums, which may include negative numbers, and a positive integer k, return the length of the shortest non-empty contiguous run whose sum is at least k. If no run reaches k, return -1.
Examples
Input: nums = [2, -1, 2], k = 3
Output: 3
Why: only the whole list sums to 3Input: nums = [84, -37, 32, 40, 95], k = 167
Output: 3
Why: 32 + 40 + 95 = 167; the whole list sums to 214 but is longerInput: nums = [1, 2], k = 4
Output: -1
Why: edge case, even the whole list falls shortHints
0 / 3
With only positive numbers a sliding window works, but a negative number breaks it: shrinking the window can raise its sum. Switch to prefix sums, where the sum of nums[i:j] is prefix[j] - prefix[i].
For each end j you want the latest start i with prefix[i] <= prefix[j] - k. A start i is useless if some later start has a prefix that is not larger, because the later one gives a shorter run with at least as large a sum.
Keep candidate starts in a deque with increasing prefix values. For each j: pop from the front while prefix[j] - prefix[front] >= k, recording j - front, since no later end can do better with that start; then pop from the back while prefix[back] >= prefix[j]; then append j.
Solution
Prefix sums turn "a run summing to at least k" into "a pair i < j with prefix[j] - prefix[i] >= k", and the goal becomes the pair with the smallest j - i. The deque holds the starts still worth trying, with their prefix values increasing from front to back, the same monotonic deque that answers sliding window maximum. Two pruning rules keep it small. From the back: a start whose prefix is at least prefix[j] can never beat j as a start, since j is later and not larger. From the front: once a start works for end j, any later end would only make that run longer, so the start is recorded and dropped. Every index enters and leaves the deque at most once, so time is O(n) and space is O(n).
from collections import deque
def shortest_run(nums, k):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
best = len(nums) + 1
starts = deque() # candidate starts, prefix values increasing
for j, p in enumerate(prefix):
while starts and p - prefix[starts[0]] >= k:
best = min(best, j - starts.popleft()) # no later end can beat this for that start
while starts and prefix[starts[-1]] >= p:
starts.pop() # j is a later and no larger start
starts.append(j)
return best if best <= len(nums) else -1
print(shortest_run([2, -1, 2], 3)) # -> 3
print(shortest_run([84, -37, 32, 40, 95], 167)) # -> 3
print(shortest_run([1, 2], 4)) # -> -1Stuck on the idea rather than the code? Sliding Window Maximum covers it.