Shortest run of trades reaching a target cost

Question

You have a stream of non-negative trade costs and a target T. Find the length of the shortest contiguous run of trades whose total cost is at least T. If no run reaches T, return 0.

costs = [2, 3, 1, 2, 4, 3], T = 7
-> 2            # the run [4, 3] already hits 7

Return the minimum length of a contiguous run summing to at least T. Aim for $O(n)$ .

Accepted Answer

Grow a window on the right, adding each cost to a running sum. Whenever the sum reaches T, the window is valid, so record its length and then shrink from the left as far as possible while it stays valid, a shorter valid window may hide inside. Because all costs are non-negative, shrinking only lowers the sum, so the "shrink while valid" loop is safe and each index is added and removed at most once. Tracing [2, 3, 1, 2, 4, 3] with T = 7: the window [2, 3, 1, 2] first reaches 8, shrinks to length 4; later [4, 3] reaches 7 at length 2, which wins. Time O(n), space O(1). Two edge cases: a target …

Shortest run of trades reaching a target cost

Your answer

More Coding questions