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
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func shortestRunReaching(crates []int, target int) int {
}Worked examples
| Call | Result |
|---|---|
shortestRunReaching([]int{2, 3, 1, 2, 4, 3}, 7) | 2 |
shortestRunReaching([]int{1, 1, 1, 1}, 4) | 4 |
shortestRunReaching([]int{1, 1}, 5) | 0 |
shortestRunReaching([]int{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 Go
func shortestRunReaching(crates []int, target int) int {
if target <= 0 {
return 0
}
left, window, best := 0, 0, 0
for right := 0; right < len(crates); right++ {
window += crates[right]
for window >= target {
span := right - left + 1
if best == 0 || span < best {
best = span
}
window -= crates[left]
left++
}
}
return best
}