The longest run of requests under a byte budget
A proxy logs the size of every response it forwarded, in order. You are given those sizes and a byte budget.
Return the length of the longest contiguous run of responses whose sizes add up to the budget or less. Sizes are non-negative; a budget of zero with no zero-sized responses means the answer is zero.
The log is long. A solution that tries every start and end is O(n²) and will time out on the last case; the sliding-window lesson has the O(n) shape.
Example
- input
sizes = [2, 1, 5, 1, 3, 2], budget = 7output3[1, 5, 1] sums to 7 and is three long; [1, 3, 2] sums to 6 and is also three long; nothing longer fits.
Constraints
- 0 ≤ sizes.length ≤ 1,000,000
- 0 ≤ each size ≤ 1,000,000,000
- 0 ≤ budget ≤ 10¹⁵ — sums need a long
Hints
Hint 1
Two indices. Advance the right one and add; while the sum is over budget, advance the left one and subtract.
Hint 2
The window only ever grows or slides right, so each index moves at most n times: O(n) in total.
Hint 3
Sizes are non-negative, which is what makes shrinking from the left correct. With negatives this shape breaks, and a prefix-sum map is the answer instead.
Stuck? The lesson behind this problem: 🧮 Two pointers and sliding window
java
Tab indents · Escape first to tab out
Test cases
These are the specification. Run tests checks your answer against them.
| Case | Input | Expected |
|---|---|---|
| the example | sizes = [2,1,5,1,3,2], budget = 7 | 3 |
| everything fits | sizes = [1,1,1], budget = 100 | 3 |
| nothing fits | sizes = [8,9], budget = 7 | 0 |
| zeros count | sizes = [0,0,5,0], budget = 0 | 2 |
| a long log | one million sizes of 1, budget = 999,999 | 999999 |