A card game is scored round by round, and nums[i] is how many points you won in round i. A bad round loses points, so values can be negative. Write shortest_subarray(nums, k) -> int that returns the length of the shortest run of consecutive rounds whose total is at least k, or -1 if no run reaches k.
shortest_subarray([4, -1, 2, 1], 6) # 4 (it takes every round)
shortest_subarray([1, -3, 2, 2], 4) # 2 ([2, 2])
shortest_subarray([5, -10, 3, 4, -1, 6], 9) # 3 ([4, -1, 6])
shortest_subarray([-2, -1], 1) # -1
This is the same question as Minimum Size Subarray Sum, except that rounds can lose points. That changes the solution: there, every value was positive, so a two-pointer window that grows on the right and shrinks on the left was enough. Here, adding a round can lower the total and dropping one can raise it, so the window gives wrong answers. In the second example it never gets past a total of 2.
Constraints:
1 <= len(nums) <= 2 * 10^5and-10^5 <= nums[i] <= 10^5.1 <= k <= 10^11. Totals can exceed 32 bits (use 64-bit integers in C++/Java).- ⭐ Bonus: trying every start with every end is O(n²) and still passes; speed tests with 200,000 rounds earn a star in O(n).
Show hint
With prefix sums P, the run from round i to round j - 1 totals P[j] - P[i], so you want the closest earlier i with P[i] <= P[j] - k. An earlier start whose prefix sum is at least as high as a later one's is never worth keeping. What's left forms an increasing sequence. Which of those starts can you also throw away for good once they have been used?