Problems › TypeScript › patterns
The quickest way to fill the order
Crates come off a belt in a fixed order. A picker wants the shortest unbroken run of crates that together hold at least what the order needs.
- Only consecutive crates count — the run cannot skip one.
- Every crate holds zero or more units; none are negative.
- Return the number of crates in the shortest run that reaches the target.
- If no run reaches it, return 0.
- A target of zero or less is already met, so the answer is 0.
shortestRunReaching(crates: list<int>, target: int) → int
Where you start
function shortestRunReaching(crates: number[], target: number): number {
}Worked examples
| Call | Result |
|---|---|
shortestRunReaching([2,3,1,2,4,3], 7) | 2 |
shortestRunReaching([1,1,1,1], 4) | 4 |
shortestRunReaching([1,1], 5) | 0 |
shortestRunReaching([8], 8) | 1 |
Hint
Grow the window on the right while it falls short, and shrink it from the left the moment it is enough. Each end only ever moves forward.
Reference solution in TypeScript
function shortestRunReaching(crates: number[], target: number): number {
if (target <= 0) return 0;
let left = 0;
let window = 0;
let best = 0;
for (let right = 0; right < crates.length; right += 1) {
window += crates[right];
while (window >= target) {
const span = right - left + 1;
if (best === 0 || span < best) best = span;
window -= crates[left];
left += 1;
}
}
return best;
}