mediumSliding WindowPattern: Sliding Window
Average Number of Events in Time Window Solution
Problem Statement
You are given two lists of integers: `timestamps` representing the time of an event and `eventCounts` representing the number of events that occurred at that timestamp. You are also given an integer `timeWindow`. Calculate the average number of events per timestamp within any contiguous sublist of `timestamps` whose duration is exactly `timeWindow`. If no such sublist exists, return 0.0. The `timestamps` list is guaranteed to be sorted in ascending order.
Examples
Example 1:
Input:timestamps = [1, 3, 5, 7, 9], eventCounts = [2, 3, 1, 4, 2], timeWindow = 4
Output:NaN
Explanation: Assuming `timeWindow` refers to the number of *timestamps* in a contiguous sublist. We need to find the average number of vehicles per timestamp for all contiguous sublists of size `timeWindow`.
1. Window [1, 3, 5, 7]: events [2, 3, 1, 4]. Total events = 10. Number of timestamps = 4. Average = 10/4 = 2.5.
2. Window [3, 5, 7, 9]: events [3, 1, 4, 2]. Total events = 10. Number of timestamps = 4. Average = 10/4 = 2.5.
The average of these window averages is (2.5 + 2.5) / 2 = 2.5.
Example 2:
Input:timestamps = [10, 20, 30, 40, 50], eventCounts = [5, 1, 8, 2, 7], timeWindow = 3
Output:NaN
Explanation: Assuming `timeWindow` refers to the number of *timestamps* in a contiguous sublist.
1. Window [10, 20, 30]: events [5, 1, 8]. Total events = 14. Number of timestamps = 3. Average = 14 / 3 = 4.666...
2. Window [20, 30, 40]: events [1, 8, 2]. Total events = 11. Number of timestamps = 3. Average = 11 / 3 = 3.666...
3. Window [30, 40, 50]: events [8, 2, 7]. Total events = 17. Number of timestamps = 3. Average = 17 / 3 = 5.666...
The average of these window averages is (4.666... + 3.666... + 5.666...) / 3 = 14.0 / 3 = 4.666...
Example 3:
Input:timestamps = [1, 2, 3], eventCounts = [10, 20, 30], timeWindow = 5
Output:NaN
Explanation: The `timeWindow` (5, interpreted as the number of timestamps in a sublist) is larger than the total number of timestamps (3). Therefore, no valid sublist of size 5 can be formed. The function returns 0.0.
Constraints
- 1 <= timestamps.length <= 10^5
- 1 <= eventCounts.length <= 10^5
- timestamps.length == eventCounts.length
- 1 <= timestamps[i] <= 10^9
- 0 <= eventCounts[i] <= 1000
- 1 <= timeWindow <= timestamps.length
- timestamps is sorted in ascending order.
Time: O(N) Space: O(1)
Utilize a sliding window technique. Calculate the sum of events for the first window of size `timeWindow`. Then, slide the window one element at a time: subtract the outgoing element's event count and add the incoming element's event count to maintain the current window's sum. For each window, calculate its average and accumulate it. The final result is the total accumulated average divided by the number of windows processed.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def average_number_of_events_in_time_window(timestamps, eventCounts, timeWindow):
n = len(timestamps)
if n == 0 or timeWindow == 0 or timeWindow > n:
return 0.0
window_sums = []
current_window_sum = 0
# Calculate sum for the first window
for i in range(timeWindow):
current_window_sum += eventCounts[i]
window_sums.append(current_window_sum)
# Slide the window
for i in range(timeWindow, n):
current_window_sum = current_window_sum - eventCounts[i - timeWindow] + eventCounts[i]
window_sums.append(current_window_sum)
total_average_sum = 0
for s in window_sums:
total_average_sum += s / timeWindow
return total_average_sum / len(window_sums)