Longest run of trades within a cost budget

Question

You have a stream of non-negative trade costs and a spending budget B. Find the maximum number of consecutive trades whose total cost stays within B.

costs = [1, 2, 1, 4, 1], B = 4
-> 3            # the run [1, 2, 1] costs 4

Return the length of the longest contiguous run with total cost at most B. Aim for $O(n)$ .

Accepted Answer

Grow a window on the right, adding each cost to a running total. Whenever the total exceeds the budget, shrink from the left, subtracting costs until the window is affordable again. Because costs are non-negative, shrinking only lowers the total, so the window is always the longest affordable run ending at the current right edge. Track the best length. Tracing [1, 2, 1, 4, 1] with B = 4: the window grows to [1, 2, 1] at cost 4 (length 3); adding the 4 overflows and forces the left edge past it, and no later window beats 3. Time O(n), left only ever moves forward, space O(1). The non-negativit…

Longest run of trades within a cost budget

Your answer

More Coding questions