Show problems as
Classic problem #209MediumArrayBinary SearchSliding WindowPrefix Sum

Minimum Size Subarray Sum

Real-world version: Fewest Shifts to Clear the Quota
Tracked in this browser only
Read Minimum Size Subarray Sum on LeetCode(opens in a new tab)

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

Learn the pattern firstSliding Window · Arrays, animated step by step

A field engineer logs the hours worked on each day of a tour, day by day, in hours.

Payroll wants to credit one unbroken run of days whose logged hours add up to quota or more, and it wants that run to cover as few days as it can. The run has to be consecutive days: skipping a day inside it is not allowed.

Return the number of days in the shortest qualifying run. When no run of consecutive days reaches quota, return 0.

Examples

Example 1

Input
quota = 11, hours = [4, 2, 5, 1, 6, 3]
Output
3

The days logging 5, 1 and 6 add up to 12, which clears the quota with three days. No pair of neighbouring days gets past 9, so two days are never enough.

Example 2

Input
quota = 10, hours = [1, 1, 10]
Output
1

The final day alone logs 10 and clears the quota, so a single day is the shortest run even though the whole tour also qualifies.

Example 3

Input
quota = 100, hours = [1, 2, 3]
Output
0

The entire tour logs only 6 hours, so no run can reach 100 and the answer falls back to 0.

Constraints

  • 1 <= quota <= 10^9
  • 1 <= hours.length <= 10^5
  • 1 <= hours[i] <= 10^4
  • Return 0 when no run of consecutive days reaches quota

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 fewest_shifts_for_quota(quota: int, hours: list[int]) -> int:
Java
public int fewestShiftsForQuota(int quota, int[] hours)

More on the same topics