progress

~/problems / Stacks / Monotonic stack

Shortest Subarray with Sum at Least K

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~45 min GoogleAppleGoldman Sachs

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^5 and -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?

Topic: Monotonic stack. Next greater/smaller element in O(n); histogram rectangles; trapping water.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc