Variable-size windows

Sometimes the window length is the answer, not a given. Use two pointers moving the same direction: right grows the window one item at a time, and left shrinks it whenever a rule is broken.

left = 0
total = 0
for right in range(len(a)):
    total += a[right]            # grow: take a[right] in
    while total > limit:         # rule broken: shrink
        total -= a[left]
        left += 1
    # here a[left..right] obeys the rule

This is valid when growing can only make the rule harder to keep, and shrinking can only make it easier. With all non-negative numbers and a "total at most" rule, that holds. Each pointer only moves forward, so the loop is about 2n steps rather than n * n.

Use while, not if, to shrink: one big new item may force several to leave. The window length at any moment is right - left + 1.

In the table, watch right push the total up and left pull it back under the limit.

See it run

nums = [2, 1, 3, 1, 1]
limit = 5
left = 0
total = 0
for right in range(len(nums)):
    total += nums[right]
    while total > limit:
        total -= nums[left]
        left += 1

right grows the window; left shrinks it whenever the total goes over the limit of 5.

Practice variable-size windows

Exercise 1

A drone can carry at most limit kg of cargo in one trip, and it must take parcels from the belt in a consecutive run (neighbours on the belt). Write solution(weights, limit) to return the largest number of parcels in a run whose total weight is at most limit.

Rules:

Weights are integers of 0 or more.
If even a single parcel is heavier than limit everywhere (no run fits), return 0.
A run has at least one parcel to count.

Constraints: 0 ≤ len(weights) ≤ 10^5; 0 ≤ limit ≤ 10^9. Your solution must be fast on 10^4 parcels with a long fitting run.

Example: solution([2, 1, 3, 1, 1], 5) returns 3: the runs [1, 3, 1] and [3, 1, 1] weigh 5; no run of 4 fits. And solution([5, 1, 3, 1], 6) returns 3 (the run [1, 3, 1] weighs 5).

Exercise 2

A warehouse shelf holds boxes in a row; boxes[i] is the number of items in box i. A picker takes a consecutive run of boxes and needs at least target items in total. Write solution(boxes, target) to return the fewest boxes in a run that reaches at least target items.

Rules:

Every box holds a positive number of items.
If even all boxes together are below target, return 0.
target is at least 1.

Constraints: 0 ≤ len(boxes) ≤ 10^5; 1 ≤ boxes[i] ≤ 10^4; 1 ≤ target ≤ 10^9. Your solution must be fast on 10^4 boxes with a large target.

Example: solution([2, 3, 1, 2, 4, 3], 7) returns 2: the boxes 4 and 3 hold 7 items; no single box does.

Exercise 3

A catering team can serve any consecutive run of dishes from a menu, as long as the dishes in the run cost at most budget in total. Write solution(costs, budget) to return how many different runs are allowed.

Rules:

A run is a non-empty consecutive slice, identified by its start and end positions; equal-looking runs at different positions count separately.
Costs are integers of 0 or more.
Return an integer; it is 0 if no run fits.

Constraints: 0 ≤ len(costs) ≤ 10^5; 0 ≤ budget ≤ 10^9. The answer can be large (up to about 5·10^9). Your solution must be fast on 10^4 dishes.

Example: solution([1, 2, 3], 3) returns 4: the runs [1], [2], [3] and [1, 2] fit; [2, 3] and [1, 2, 3] do not.

The explanation and tasks are public. Running this lesson requires an account with course access.

Practice

Loading Python…

Loading exercise content…

Visualizer Watch your code run line by line

Run your code, then choose Play to follow its execution.

Memory · names → values

Variables appear here as Python creates them.

Output & plots