Show problems as
Classic problem #862HardArrayBinary SearchQueueSliding WindowHeap (Priority Queue)Prefix SumMonotonic Queue

Shortest Subarray with Sum at Least K

Real-world version: Shortest Run Meeting the Grid Quota
Tracked in this browser only
Read Shortest Subarray with Sum at Least K on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tidal power station logs its net contribution to the grid once a minute. net[i] is the number of kilowatt-hours the station delivered during minute i, and the figure is negative for a minute in which the station drew more from the grid than it delivered, which happens while the sluices are being refilled around slack water.

A run is a block of one or more consecutive minutes, and its yield is the total of the logged figures across those minutes.

The operator has to show one run whose yield is at least quota, and wants the shortest such run. Return the number of minutes in the shortest run whose yield is at least quota. If no run reaches quota at all, return -1.

Examples

Example 1

Input
net = [4, -1, 4], quota = 7
Output
3

The three minutes together yield 4 - 1 + 4 = 7, which meets the quota; neither single minute nor either pair of neighbouring minutes reaches 7.

Example 2

Input
net = [1, 1, 100], quota = 2
Output
1

The last minute on its own yields 100, comfortably past a quota of 2, and a run cannot be shorter than one minute.

Example 3

Input
net = [17], quota = 18
Output
-1

The log holds one run, and its yield of 17 falls short of the quota.

Example 4

Input
net = [3, -2, 6, -1, 4], quota = 9
Output
3

The last three minutes yield 6 - 1 + 4 = 9, exactly the quota, while no single minute and no neighbouring pair reaches 9.

Constraints

  • 1 <= net.length <= 10^5
  • -10^5 <= net[i] <= 10^5
  • 1 <= quota <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shortest_run(net: list[int], quota: int) -> int:
Java
public int shortestRun(int[] net, int quota)

More on the same topics