Design an algorithm to process a time-series metric stream and compute the average value over a sliding window of fixed duration (e.g., 1-minute window). Optimize for time and space complexity, and explain how this relates to real-time monitoring in Prometheus.

To process a time-series metric stream with a sliding window, use a deque to maintain the window's elements and a running sum for efficient average calculation. When a new data point arrives, add it to the deque and update the sum. Remove outdated elements outside the window's time range. The average is computed by dividing the sum by the deque's length. This approach ensures O(1) time complexity for each insertion and average calculation, with O(n) space complexity for the window size. In Prometheus, this aligns with its time-series aggregation model, where metrics are stored and queried over time ranges, requiring efficient sliding window computations for real-time dashboards and alerts.

The algorithm uses a deque to store the time-series data points within the sliding window and a running sum to avoid recalculating the total each time. When a new data point arrives, it is added to the deque, and the sum is updated. If the oldest element in the deque falls outside the window's time range, it is removed from the front. The average is then computed by dividing the sum by the number of elements in the deque. This ensures O(1) time complexity for each insertion and average calculation, as each operation (append, pop, sum update) is constant time. Space complexity is O(n), where n is the maximum number of elements in the window. In Prometheus, this approach mirrors how metrics are aggregated over time intervals using range vectors and functions like avg_over_time(), enabling efficient real-time monitoring and alerting with minimal latency and resource usage.