Longest streak of days within a budget

Sliding window Junior Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

spend, budget = [2, 1, 3, 4, 1, 1, 2], 5
total = left = best = 0
for right, x in enumerate(spend):
    total += x
    while total > budget:
        total -= spend[left]
        left += 1
    best = max(best, right - left + 1)
print(best, left)

Options3 42 43 0

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 4

Right: the days [4, 1] then [1, 1, 2] fit; the last window starts at index 4 and has length 3.

The best run [1, 1, 2] totals 4, and the earlier run [2, 1] is shorter, so the answer and the final left pointer come from the end of the list.

Why not the others?

B 2 4. The window [1, 1, 2] at the end totals 4, which fits, so the best length reaches 3.
C 3 0. The left pointer moves forward several times; it ends at index 4.

A window over daily spending [2, 1, 3, 4, 1, 1, 2] grows on the right and shrinks on the left whenever the total passes the budget.

Steps come from running the Python solution.

Text version

Budget 5:

Cells: [2, 1, 3, 4, 1, 1, 2]

L = 0, R = 0. Window total = 2. Add day 0: total 2; best 1
L = 0, R = 1. Window total = 3. Add day 1: total 3; best 2
L = 0, R = 2. Window total = 6. Add day 2: total 6
L = 1, R = 2. Window total = 4. Over 5: drop a day, total 4
L = 1, R = 3. Window total = 8. Add day 3: total 8
L = 2, R = 3. Window total = 7. Over 5: drop a day, total 7
L = 3, R = 3. Window total = 4. Over 5: drop a day, total 4
L = 3, R = 4. Window total = 5. Add day 4: total 5
L = 3, R = 5. Window total = 6. Add day 5: total 6
L = 4, R = 5. Window total = 2. Over 5: drop a day, total 2
L = 4, R = 6. Window total = 4. Add day 6: total 4; best 3

Result: 3

Budget 8:

Cells: [2, 1, 3, 4, 1, 1, 2]

L = 0, R = 0. Window total = 2. Add day 0: total 2; best 1
L = 0, R = 1. Window total = 3. Add day 1: total 3; best 2
L = 0, R = 2. Window total = 6. Add day 2: total 6; best 3
L = 0, R = 3. Window total = 10. Add day 3: total 10
L = 1, R = 3. Window total = 8. Over 8: drop a day, total 8
L = 1, R = 4. Window total = 9. Add day 4: total 9
L = 2, R = 4. Window total = 8. Over 8: drop a day, total 8
L = 2, R = 5. Window total = 9. Add day 5: total 9
L = 3, R = 5. Window total = 6. Over 8: drop a day, total 6
L = 3, R = 6. Window total = 8. Add day 6: total 8; best 4

Result: 4

30-second answer

Grow a window one day at a time on the right and keep its total. While the total is over budget, drop days from the left. After each step the window is the longest valid run ending at that day, so the best length seen is the answer. Each day enters and leaves once: O(n) time, O(1) space.

Practise saying it · 60 s. No recording, just a timer

Walk through the variable sliding window.

Say your answer out loud, then check which of these points you covered:

Grow right, shrink left
Non-negative amounts make it safe
Each pointer moves at most n times

Deep dive

Non-negative amounts are what make shrinking safe: removing a day can only lower the total.

The inner while loop looks quadratic, but left moves at most n times over the whole run.

Checking every start and end pair is O(n²) (with running sums) or O(n³) (without).

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def longest_streak(spend: list[int], budget: int) -> int:
    total = left = best = 0
    for right, x in enumerate(spend):
        total += x
        while total > budget:
            total -= spend[left]
            left += 1
        best = max(best, right - left + 1)
    return best

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun longestStreak(spend: List<Int>, budget: Int): Int {
    var total = 0
    var left = 0
    var best = 0
    for (right in spend.indices) {
        total += spend[right]
        while (total > budget) {
            total -= spend[left]
            left++
        }
        best = maxOf(best, right - left + 1)
    }
    return best
}

Common mistakes

Using if instead of while to shrink, which leaves the window over budget after a big day.
Updating best before the shrink loop finishes.

Senior take & follow-ups

Explain the amortised argument for the inner loop; interviewers ask about it nearly every time.

Follow-up questions

Think of your answer first, then open the hint.

What if amounts can be negative?
Show hint
Shrinking is no longer safe; use prefix sums with a sorted structure, or a different approach.
How would you return the days themselves?
Show hint
Record left and right whenever best improves.

See it animated on iPhone (Arrays in DSA Master - Data & Algorithms)

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.