Design an Array Statistics Tracker - Video Solutions

Problem Overview: You need to design a data structure that continuously tracks statistics of numbers added to an array. Operations update the structure dynamically while supporting fast queries for statistics such as mean, median, and mode. The challenge is keeping these values updated efficiently as elements are inserted and removed.

Approach 1: Recompute Statistics on Every Query (Brute Force) (Time: O(n log n) per query, Space: O(n))

The simplest design stores all elements in a list. When a statistic is requested, recompute it from scratch. Mean requires iterating through the entire array. Median requires sorting the array or maintaining a temporary sorted copy, which costs O(n log n). Mode requires counting frequencies using a map. This approach works for small inputs but quickly becomes inefficient when the number of updates or queries grows.

Approach 2: Queue + Hash Table + Ordered Set (Time: O(log n) updates, O(1)–O(log n) queries, Space: O(n))

An efficient implementation combines multiple data structures to maintain statistics incrementally. A queue preserves insertion order so you can remove the oldest element when required. A hash table stores element frequencies, allowing constant-time updates for mode tracking. To maintain sorted order for median queries, use an ordered structure such as a balanced tree or sorted list that supports insertion and deletion in O(log n). These ordered structures rely on ideas similar to binary search for positioning elements efficiently.

Whenever a value is added, push it into the queue, update the frequency map, and insert it into the ordered set. When removing the oldest value, pop from the queue, decrement its frequency in the hash table, and delete it from the ordered set. Mean can be maintained incrementally using a running sum. Median comes directly from the middle element of the ordered set. Mode is tracked by maintaining the highest frequency from the map.

This design avoids full recomputation. Each update touches only the structures affected by the inserted or removed value. Ordered sets guarantee logarithmic updates, while hash lookups remain constant time. The result is a scalable tracker capable of handling frequent updates and queries.

Recommended for interviews: Interviewers expect the multi–data structure approach using a queue, hash table, and ordered structure. Explaining the brute force approach first shows understanding of the statistical requirements, but the optimized design demonstrates your ability to maintain dynamic order and frequency efficiently in O(log n) time.