Moving Average from Data Stream
Overview
Moving average from data stream is a problem where you need to calculate the average of the last k elements in a stream of numbers. A queue is the perfect data structure for this because it maintains a sliding window of the most recent k elements, automatically removing the oldest element when a new one arrives.
This problem demonstrates:
- Sliding window - Maintain window of last k elements
- FIFO order - Oldest element removed first
- Efficient updates - O(1) update when new element arrives
- Real-time calculations - Calculate average as data streams in
Key characteristics:
- Fixed window size - Maintain exactly k elements
- Sliding window - Window slides as new data arrives
- Queue-based - Queue maintains window order
- O(1) update - Constant time for each new element
- Running average - Calculate average efficiently
How Moving Average Works
Moving average uses a queue to maintain a sliding window:
- Initialize - Create queue with capacity k
- Add element - Enqueue new element
- Remove old - If queue full, dequeue oldest element
- Calculate average - Sum elements in queue, divide by count
- Return average - Return current moving average
The queue automatically maintains the window of last k elements.
Basic Moving Average Implementation
Simple moving average using queue:
class MovingAverage {
private queue: number[] = [];
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
}
next(val: number): number {
// Add new value
this.queue.push(val);
this.sum += val;
// Remove oldest if window exceeded
if (this.queue.length > this.size) {
const removed = this.queue.shift()!;
this.sum -= removed;
}
// Calculate and return average
return this.sum / this.queue.length;
}
}Time: O(1) amortized, O(n) worst case with shift(), Space: O(k)
Limitation: shift() is O(n), making this inefficient.
Pattern 1: LeetCode - Moving Average from Data Stream
LeetCode problem with efficient implementation:
class MovingAverage {
private queue: number[] = [];
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
}
next(val: number): number {
this.queue.push(val);
this.sum += val;
if (this.queue.length > this.size) {
const removed = this.queue.shift()!;
this.sum -= removed;
}
return this.sum / this.queue.length;
}
}Time: O(1) amortized, Space: O(k)
Key insight: Track sum to avoid recalculating.
Pattern 2: Circular Queue for Moving Average
Using circular queue for true O(1) operations:
class MovingAverageCircular {
private queue: number[];
private front = 0;
private rear = -1;
private count = 0;
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
this.queue = new Array(size).fill(0);
}
next(val: number): number {
// If queue is full, remove oldest
if (this.count === this.size) {
this.sum -= this.queue[this.front];
this.front = (this.front + 1) % this.size;
this.count--;
}
// Add new value
this.rear = (this.rear + 1) % this.size;
this.queue[this.rear] = val;
this.sum += val;
this.count++;
return this.sum / this.count;
}
}Time: O(1) true constant time, Space: O(k)
Key optimization: Circular queue avoids shift() overhead.
Pattern 3: Moving Average with Linked List
Using linked list for O(1) operations:
class ListNode {
val: number;
next: ListNode | null = null;
constructor(val: number) {
this.val = val;
}
}
class MovingAverageLinkedList {
private head: ListNode | null = null;
private tail: ListNode | null = null;
private count = 0;
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
}
next(val: number): number {
const newNode = new ListNode(val);
// Add to rear
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail!.next = newNode;
this.tail = newNode;
}
this.sum += val;
this.count++;
// Remove from front if exceeded size
if (this.count > this.size) {
const removed = this.head!.val;
this.head = this.head!.next;
if (this.head === null) {
this.tail = null;
}
this.sum -= removed;
this.count--;
}
return this.sum / this.count;
}
}Time: O(1), Space: O(k)
Key advantage: True O(1) operations with linked list.
Pattern 4: Multiple Moving Averages
Track multiple moving averages simultaneously:
class MultipleMovingAverages {
private windows: Map<number, { queue: number[], sum: number }> = new Map();
addWindow(size: number): void {
this.windows.set(size, { queue: [], sum: 0 });
}
next(val: number): Map<number, number> {
const averages = new Map<number, number>();
for (const [size, window] of this.windows) {
window.queue.push(val);
window.sum += val;
if (window.queue.length > size) {
const removed = window.queue.shift()!;
window.sum -= removed;
}
averages.set(size, window.sum / window.queue.length);
}
return averages;
}
}Time: O(w) where w is number of windows, Space: O(w × k)
Use case: Track multiple time periods (5-day, 10-day, 20-day averages).
Pattern 5: Exponential Moving Average
Weighted moving average (more recent values weighted higher):
class ExponentialMovingAverage {
private queue: number[] = [];
private size: number;
private alpha: number; // Smoothing factor (0 < alpha <= 1)
private ema: number | null = null;
constructor(size: number, alpha: number = 0.3) {
this.size = size;
this.alpha = alpha;
}
next(val: number): number {
this.queue.push(val);
if (this.queue.length > this.size) {
this.queue.shift();
}
// Calculate EMA
if (this.ema === null) {
// Initialize with first value
this.ema = val;
} else {
// EMA formula: EMA = alpha * current + (1 - alpha) * previous EMA
this.ema = this.alpha * val + (1 - this.alpha) * this.ema;
}
return this.ema;
}
}Time: O(1), Space: O(k)
Key insight: Exponential moving average gives more weight to recent values.
Pattern 6: Moving Average with Outliers
Moving average that ignores outliers:
class MovingAverageRobust {
private queue: number[] = [];
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
}
next(val: number): number {
this.queue.push(val);
if (this.queue.length > this.size) {
const removed = this.queue.shift()!;
this.sum -= removed;
}
this.sum += val;
// Calculate average excluding outliers
const sorted = [...this.queue].sort((a, b) => a - b);
const trim = Math.floor(this.queue.length * 0.1); // Remove 10% outliers
const trimmed = sorted.slice(trim, sorted.length - trim);
const trimmedSum = trimmed.reduce((a, b) => a + b, 0);
return trimmedSum / trimmed.length;
}
}Time: O(k log k) due to sorting, Space: O(k)
Key insight: Remove outliers before calculating average.
Pattern 7: Moving Average with Minimum/Maximum
Track moving average along with min/max:
class MovingAverageWithMinMax {
private queue: number[] = [];
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
}
next(val: number): { avg: number, min: number, max: number } {
this.queue.push(val);
this.sum += val;
if (this.queue.length > this.size) {
const removed = this.queue.shift()!;
this.sum -= removed;
}
const avg = this.sum / this.queue.length;
const min = Math.min(...this.queue);
const max = Math.max(...this.queue);
return { avg, min, max };
}
}Time: O(k) for min/max, Space: O(k)
Key insight: Can track additional statistics.
When to Use Queue for Moving Average
Use queue for moving average when you see:
- "Moving average" - Average of last k elements
- "Sliding window" - Fixed-size window over stream
- "Data stream" - Continuous stream of data
- "Last k values" - Need to track recent values
- "Running average" - Calculate average as data arrives
- "Time series" - Time-series data analysis
- "Real-time" - Real-time average calculation
Key distinction:
- Queue - Perfect for sliding window, maintains order
- Array - Can work but less efficient
- Circular buffer - Most efficient for fixed size
Moving Average Patterns
| Pattern | Description | Use Case |
|---------|-------------|----------|
| Simple | Equal weight to all values | General purpose |
| Exponential | More weight to recent values | Trend analysis |
| Weighted | Custom weights | Custom analysis |
| Robust | Ignores outliers | Noisy data |
| Multiple | Track multiple windows | Multi-timeframe |
Remember:
- Queue for sliding window maintenance
- Track sum to avoid recalculating
- Circular queue for true O(1) operations
Template (Basic Moving Average)
class MovingAverageTemplate {
private queue: number[] = [];
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
}
next(val: number): number {
this.queue.push(val);
this.sum += val;
if (this.queue.length > this.size) {
const removed = this.queue.shift()!;
this.sum -= removed;
}
return this.sum / this.queue.length;
}
}Template (Circular Queue Moving Average)
class MovingAverageCircularTemplate {
private queue: number[];
private front = 0;
private rear = -1;
private count = 0;
private size: number;
private sum = 0;
constructor(size: number) {
this.size = size;
this.queue = new Array(size).fill(0);
}
next(val: number): number {
if (this.count === this.size) {
this.sum -= this.queue[this.front];
this.front = (this.front + 1) % this.size;
this.count--;
}
this.rear = (this.rear + 1) % this.size;
this.queue[this.rear] = val;
this.sum += val;
this.count++;
return this.sum / this.count;
}
}Time and Space Complexity
Basic Implementation (with shift)
- next: O(1) amortized, O(k) worst case
- Space: O(k)
Circular Queue Implementation
- next: O(1) true constant time
- Space: O(k)
Linked List Implementation
- next: O(1)
- Space: O(k)
Note: Circular queue or linked list provides true O(1) operations.
Practice Tips
- Track sum - Maintain running sum to avoid recalculating
- Use circular queue - For true O(1) operations
- Handle edge cases - Empty queue, less than k elements
- Avoid shift() - Use circular queue or linked list
- Precision - Consider floating point precision issues
- Window size - Handle window size changes if needed
- Multiple windows - Can track multiple averages simultaneously
Common Mistakes
- Using shift() - O(k) operation, use circular queue instead
- Recalculating sum - Not tracking sum, recalculating each time
- Wrong window size - Not handling window size correctly
- Edge cases - Not handling when queue has less than k elements
- Precision errors - Floating point precision issues
- Not removing old - Forgetting to remove oldest element
- Index errors - Off-by-one errors in circular queue
Real-World Applications
Moving average is used extensively in:
- Finance - Stock price analysis, technical indicators
- Signal Processing - Noise reduction, smoothing
- Time Series Analysis - Trend analysis, forecasting
- Sensor Data - Smoothing sensor readings
- Performance Monitoring - CPU usage, network throughput
- Analytics - User behavior, metrics tracking
- Trading Algorithms - Technical analysis, indicators
- IoT - Sensor data smoothing
Related Concepts
- Queue - Data structure for sliding window
- Circular Queue - Efficient implementation
- Sliding Window - General sliding window pattern
- Time Series - Time-series data analysis
- Statistics - Statistical analysis
Summary
Moving average from data stream demonstrates:
- Sliding window - Maintain window of last k elements
- Queue-based - Queue maintains window order
- Efficient updates - O(1) update with sum tracking
- Real-time - Calculate average as data streams
- Fixed window - Maintain exactly k elements
Key takeaways:
- Use queue to maintain sliding window
- Track sum to avoid recalculating
- Use circular queue for true O(1) operations
- Essential for time-series and streaming data
- Foundation for many analytics applications
Mastering moving average with queue will help you solve sliding window problems, handle streaming data, and implement efficient real-time calculations in coding interviews.