Fixed Window Example: The Busiest Three Hours of a Shop's Day

Hourly footfall and a window of exactly three hours: add the hour entering, subtract the hour leaving, and keep the largest sum.

A fixed window updates its sum with one addition and one subtraction per step, so the best of every run of k elements costs O(n) rather than O(n × k). A shop counted its visitors in each of nine opening hours: 4 2 7 1 8 3 6 2 5. The manager wants the three consecutive hours with the most visitors, to staff them first.

Recomputing each window adds k values, and a day of n hours holds n − k + 1 windows: 7 here. Sliding avoids the recount. Build the first window's sum once, then at each step add the hour entering on the right and subtract the hour leaving on the left, which costs O(1) whatever the window's size.

A window of 3 hours over the footfall 4 2 7 1 8 3 6 2 5

Inputvisitors per hour 4 2 7 1 8 3 6 2 5, window 3

Hours 0 to 2
1. 4start
2. 2
3. 7end
4. 1
5. 8
6. 3
7. 6
8. 2
9. 5
first window built: 4 + 2 + 7 = 13, best 13
Hours 1 to 3
1. 4
2. 2start
3. 7
4. 1end
5. 8
6. 3
7. 6
8. 2
9. 5
added 1, removed 4: sum 10, best 13
Hours 2 to 4
1. 4
2. 2
3. 7start
4. 1
5. 8end
6. 3
7. 6
8. 2
9. 5
added 8, removed 2: sum 16, best 16
Hours 3 to 5
1. 4
2. 2
3. 7
4. 1start
5. 8
6. 3end
7. 6
8. 2
9. 5
added 3, removed 7: sum 12, best 16
Hours 4 to 6
1. 4
2. 2
3. 7
4. 1
5. 8start
6. 3
7. 6end
8. 2
9. 5
added 6, removed 1: sum 17, best 17
Hours 5 to 7
1. 4
2. 2
3. 7
4. 1
5. 8
6. 3start
7. 6
8. 2end
9. 5
added 2, removed 8: sum 11, best 17
Hours 6 to 8
1. 4
2. 2
3. 7
4. 1
5. 8
6. 3
7. 6start
8. 2
9. 5end
added 5, removed 3: sum 13, best 17

ResultThe busiest three hours are 8 3 6, with 17 visitors.

The listing finds the busiest window and returns where it starts, then asks for a three-hour window over a day of two hours.

footfall.pypy

def busiest(hours: list[int], k: int) -> tuple[int, int] | None:
    if len(hours) < k:
        return None
    total = sum(hours[:k])
    best, best_start = total, 0
    for end in range(k, len(hours)):
        total += hours[end] - hours[end - k]
        if total > best:
            best, best_start = total, end - k + 1
    return best, best_start


footfall = [4, 2, 7, 1, 8, 3, 6, 2, 5]
best, first = busiest(footfall, 3)
print("footfall", *footfall, "window 3: busiest", *footfall[first:first + 3], "=", best)
print("2 hours, window 3:", busiest([4, 2], 3))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

footfall 4 2 7 1 8 3 6 2 5 window 3: busiest 8 3 6 = 17
2 hours, window 3: None

The busiest hours are the fifth, sixth and seventh, with 17 visitors, and a day shorter than the window has no window at all, so the function returns None rather than a sum of fewer hours. The pass is O(n) time and O(1) extra space for n hours. A fixed window works on negative values too, because its length, not its sum, decides when start moves.

Sliding Window

← → move through sections and cards