Solution: Keeping a Running Sum

Think of the window as a queue that holds the last k readings.

The direct way to get the average is to add up the window on every call. With our Queue, that is not a single operation: the interface has no way to iterate over the items, so summing the window means dequeuing all k readings and enqueuing each one back as we go. It works, and the window ends up unchanged, but every add ends up costing $O(k)$. The problem asks for $O(1)$.

The fix is a running sum: a field that always holds the sum of the readings currently in the window. When a reading enters the window, we add it to the sum, and when a reading leaves, we subtract it. Each add changes the sum at most twice, and then the average is one division.

You might ask: if the sum is maintained in a field, why keep the queue at all? We need the queue for the subtraction. When the window is full, add must subtract the reading that leaves, so it needs the value of that reading. The sum and the count cannot tell us what that value was. The queue stores the last k readings in arrival order and gives us the oldest one. Without it, we could compute the average of all readings so far, but not a moving average, because we would have no way to drop old readings.

public class MovingAverage {
  private Queue<Integer> window = new LinkedQueue<>();
  private int k;
  private int count;  // how many readings are in the window
  private int sum;    // the sum of the readings in the window

  public MovingAverage(int k) {
    if (k < 1) {
      throw new IllegalArgumentException();
    }
    this.k = k;
  }

  public double add(int reading) {
    window.enqueue(reading);
    sum += reading;
    count++;
    if (count > k) {
      int oldest = window.front();  // look at the reading that must leave
      window.dequeue();             // then remove it
      sum -= oldest;
      count--;
    }
    return (double) sum / count;
  }
}

A few things to notice:

• Removing the oldest reading uses the front-then-dequeue pairing. dequeue does not return the removed item, so we read it with front first and then remove it with dequeue.
• Our Queue has no operation that reports its size, so the count field counts the readings itself. The if runs at most once per call. Each add grows count by one, and the if brings it back to k right away. So the window never holds more than k + 1 readings, and it only holds k + 1 for a moment inside a single add call.
• Both sum and count are int. Without the cast in (double) sum / count, Java does integer division and throws away the remainder. Casting one operand first makes the division produce a double.
• Until the window fills up, the if never runs, and the divisor is count, not k, so the early calls return the average of the readings so far, as the contract asks. With k = 1, every call after the first removes the previous reading, and the average is just the latest one.

Let’s trace! Suppose k is 3 and the queue already holds 6, 2, 7, with sum 15 and count 3:

┌───┬───┬───┐
│ 6 │ 2 │ 7 │
└───┴───┴───┘
  ▲       ▲
front   back

Now we call add(3). The new reading is enqueued, making sum 18 and count 4. The window now holds four readings, one more than k:

┌───┬───┬───┬───┐
│ 6 │ 2 │ 7 │ 3 │
└───┴───┴───┴───┘
  ▲           ▲
front       back

Now count > k, so the if reads the front reading 6, dequeues it, and subtracts it from the sum, bringing sum to 12 and count back to 3:

┌───┬───┬───┐
│ 2 │ 7 │ 3 │
└───┴───┴───┘
  ▲       ▲
front   back

The call returns 4.0, the average of the readings in the window: 2, 7, and 3.

Each add performs one enqueue, at most one front and dequeue, and a constant number of arithmetic operations. Every queue operation is $O(1)$, so add is $O(1)$, and the auxiliary space is $O(k)$ for the queue.