Design a data structure that keeps track of the values in it and answers some queries regarding their mean, median, and mode.
Implement the StatisticsTracker class.
StatisticsTracker(): Initialize the StatisticsTracker object with an empty array.void addNumber(int number): Add number to the data structure.void removeFirstAddedNumber(): Remove the earliest added number from the data structure.int getMean(): Return the floored mean of the numbers in the data structure.int getMedian(): Return the median of the numbers in the data structure.int getMode(): Return the mode of the numbers in the data structure. If there are multiple modes, return the smallest one.Note:
Example 1:
Input:
["StatisticsTracker", "addNumber", "addNumber", "addNumber", "addNumber", "getMean", "getMedian", "getMode", "removeFirstAddedNumber", "getMode"]
[[], [4], [4], [2], [3], [], [], [], [], []]
Output:
[null, null, null, null, null, 3, 4, 4, null, 2]
Explanation
StatisticsTracker statisticsTracker = new StatisticsTracker();Example 2:
Input:
["StatisticsTracker", "addNumber", "addNumber", "getMean", "removeFirstAddedNumber", "addNumber", "addNumber", "removeFirstAddedNumber", "getMedian", "addNumber", "getMode"]
[[], [9], [5], [], [], [5], [6], [], [], [8], []]
Output:
[null, null, null, 7, null, null, null, null, 6, null, 5]
Explanation
StatisticsTracker statisticsTracker = new StatisticsTracker();
Constraints:
1 <= number <= 109105 calls will be made to addNumber, removeFirstAddedNumber, getMean, getMedian, and getMode in total.removeFirstAddedNumber, getMean, getMedian, and getMode will be called only if there is at least one element in the data structure.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.
We define a queue q to store the added numbers, a variable s to store the sum of all numbers, a hash table cnt to store the occurrence count of each number, an ordered set sl to store all numbers, and an ordered set sl2 to store all numbers and their occurrence counts, sorted by occurrence count in descending order and by value in ascending order.
In the addNumber method, we add the number to the queue q, add the number to the ordered set sl, then remove the number and its occurrence count from the ordered set sl2, update the occurrence count of the number, and finally add the number and its updated occurrence count to the ordered set sl2, and update the sum of all numbers. The time complexity is O(log n).
In the removeFirstAddedNumber method, we remove the earliest added number from the queue q, remove the number from the ordered set sl, then remove the number and its occurrence count from the ordered set sl2, update the occurrence count of the number, and finally add the number and its updated occurrence count to the ordered set sl2, and update the sum of all numbers. The time complexity is O(log n).
In the getMean method, we return the sum of all numbers divided by the number of numbers. The time complexity is O(1).
In the getMedian method, we return the len(q) / 2-th number in the ordered set sl. The time complexity is O(1) or O(log n).
In the getMode method, we return the first number in the ordered set sl2. The time complexity is O(1).
In Python, we can directly access elements in an ordered set by index. In other languages, we can implement this using a heap.
The space complexity is O(n), where n is the number of added numbers.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute Statistics (Brute Force) | O(n log n) per query | O(n) | Small datasets or when queries are rare |
| Queue + Hash Table + Ordered Set | O(log n) update, O(1)–O(log n) query | O(n) | Best for continuous updates and frequent statistic queries |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views
Watch 9 more video solutions →Practice Design an Array Statistics Tracker with our built-in code editor and test cases.
Practice on FleetCode