Shortest run of orders that reaches a goal

Sliding window Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
orders, goal = [2, 3, 1, 2, 4, 3], 7
best, total, left = 0, 0, 0
for right, x in enumerate(orders):
    total += x
    while total >= goal:
        size = right - left + 1
        best = size if best == 0 else min(best, size)
        total -= orders[left]
        left += 1
print(best)

Options

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

Show answer

Answer: A 2

Right: [4, 3] reaches 7 with two orders.

The shrink loop keeps trimming while the goal is still met, which uncovers the two-order run at the end.

Why not the others?
  • B 3. [2, 4, 3] is not the shortest; [4, 3] works too.
  • C 4. [2, 3, 1, 2] reaches 8, but shorter runs exist later.

30-second answer

Grow the window on the right; while its total reaches the goal, record its length and shrink from the left to see if a shorter run still works. Positive values make shrinking monotonic. O(n) time, O(1) space.

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

Explain the shortest-window variant.

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

  • Grow right
  • Record while shrinking
  • Positive values make it valid

Deep dive

This is the mirror of the 'longest within budget' window: record inside the shrink loop rather than after it.

With positive values, prefix sums are increasing, so binary search per end also works in O(n log n).

Return 0 (or the agreed sentinel) when the total of everything is below the goal.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def shortest_run(orders: list[int], goal: int) -> int:
    best = 0
    total = left = 0
    for right, x in enumerate(orders):
        total += x
        while total >= goal:
            size = right - left + 1
            best = size if best == 0 else min(best, size)
            total -= orders[left]
            left += 1
    return best

Common mistakes

  • Recording the length after the shrink loop, when the window no longer reaches the goal.
  • Returning infinity or n + 1 when nothing reaches the goal.

Senior take & follow-ups

Point out exactly where the answer is recorded and why; that is the difference from the 'longest' version.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if values can be zero or negative?

    Show hint

    Zeros are fine; negatives need prefix sums with a monotonic deque.

  2. Can you do it in O(n log n) another way?

    Show hint

    Binary search on prefix sums for each right end.

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.