The busiest stretch of the day
A traffic chart holds one count per minute. The headline figure is the busiest run of a fixed number of consecutive minutes.
- The window is a run of exactly `runLength` consecutive minutes.
- If the day is shorter than the window, there is no such run: return 0.
- A window size of zero or less also returns 0.
busiestStretch(perMinute: list<int>, runLength: 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 busiestStretch(perMinute []int, runLength int) int {
}Worked examples
| Call | Result |
|---|---|
busiestStretch([]int{1, 4, 2, 10, 2, 3, 1, 0, 20}, 4) | 24 |
busiestStretch([]int{2, 3}, 3) | 0 |
busiestStretch([]int{5, 5, 5}, 1) | 5 |
busiestStretch([]int{1, 2, 3}, 3) | 6 |
Hint
Total the first window, then slide: add the minute coming in and subtract the one going out. Re-adding the whole window each step is the slow way.
Reference solution in Go
func busiestStretch(perMinute []int, runLength int) int {
if runLength <= 0 || len(perMinute) < runLength {
return 0
}
window := 0
for i := 0; i < runLength; i++ {
window += perMinute[i]
}
best := window
for i := runLength; i < len(perMinute); i++ {
window += perMinute[i] - perMinute[i-runLength]
if window > best {
best = window
}
}
return best
}