League Review Stretch
Indices of the earliest longest subarray with sum at most a budget
A football league's review team wants to audit a consecutive stretch of matches. The matches are listed in chronological order, and work[i] is the number of review units needed for match i.
The team can spend at most budget review units in total. Find the longest nonempty consecutive stretch whose total work does not exceed budget.
Return [start, end], the zero-based, inclusive indices of that stretch. If several stretches have the same maximum length, return the one with the smallest starting index. If no nonempty stretch is affordable, return [-1, -1].
Work values are nonnegative, and matches requiring zero review units still count toward the length of a stretch.
Examples
Example 1
Input: work = [4,1,0,2,5], budget = 3 Output: [1,3]
Matches at indices 1 through 3 require 1 + 0 + 2 review units, exactly the available budget. No four consecutive matches are affordable.
Example 2
Input: work = [0,0,3,0,0], budget = 0 Output: [0,1]
Only stretches consisting entirely of zero-work matches fit a zero budget. The two longest such stretches have equal length, so the earlier one is selected.
Example 3
Input: work = [5,7,4], budget = 3 Output: [-1,-1]
Every individual match requires more work than the available budget, so there is no affordable nonempty stretch.
Constraints
- 0 <= work.length <= 12000
- 0 <= work[i] <= 1000
- 0 <= budget <= 1000000000
The intended solution takes O(n) time and O(1) auxiliary space. The input array must not be modified.
Hints
Show hint 1Hint 1
As you extend a stretch to the right, nonnegative work values can never decrease its total work.
Show hint 2Hint 2
Maintain a running total and move the left endpoint forward while the total exceeds the budget. Record a stretch only when it is strictly longer than the best one seen.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you count all affordable nonempty consecutive stretches instead of returning the longest one?
- If work values arrive one at a time, how could you update the best endpoints after each new match?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem