3369. Design an Array Statistics Tracker - Detailed Explanation

Problem Statement

Design a data structure that keeps track of a stream of integers and supports querying their mean, median, and mode, while also allowing removal of the earliest added element.

Implement the StatisticsTracker class:

• StatisticsTracker() Initializes the tracker with an empty collection.

• void addNumber(int number) Adds number to the tracker.

• void removeFirstAddedNumber() Removes the earliest added number from the tracker.

• int getMean() Returns the floored average (mean) of all numbers currently in the tracker.

• int getMedian() Returns the median of all numbers. If there are two middle values, return the larger one.

• int getMode() Returns the mode (most frequent value). If multiple values tie, return the smallest one.

Examples
1.

// sequence of operations  
StatisticsTracker st = new StatisticsTracker();  
st.addNumber(4);            // [4]  
st.addNumber(4);            // [4,4]  
st.addNumber(2);            // [4,4,2]  
st.addNumber(3);            // [4,4,2,3]  
st.getMean();   // returns 3   ( (4+4+2+3)/4 = 3.25 → floored to 3 )  
st.getMedian(); // returns 4   (sorted → [2,3,4,4], two middles are 3 & 4 → pick 4)  
st.getMode();   // returns 4   (4 appears twice)  
st.removeFirstAddedNumber(); // removes the first 4 → [4,2,3]  
st.getMode();   // returns 2   (all appear once → pick smallest)  

2. StatisticsTracker st = new StatisticsTracker();  
   st.addNumber(1);            // [1]  
   st.getMean();   // 1  
   st.getMedian(); // 1  
   st.getMode();   // 1  
   

3. StatisticsTracker st = new StatisticsTracker();  
   st.addNumber(5);            // [5]  
   st.addNumber(7);            // [5,7]  
   st.removeFirstAddedNumber(); // removes 5 → [7]  
   st.getMean();   // 7  
   st.getMedian(); // 7  
   st.getMode();   // 7  
   

Constraints

• Total number of method calls ≤ 10⁵.
• −10⁵ ≤ number ≤ 10⁵.
• removeFirstAddedNumber, getMean, getMedian, and getMode are only called when the tracker is non‑empty.

Hints

1. To support removal of the earliest added element, think of a queue.
2. For median queries, what data structure lets you insert, delete, and find the middle element efficiently?
3. For mode queries, how can you track frequencies and always know the most frequent (and tie‑break by smallest)?

Approach 1 Naive Scanning

Explanation

Store all numbers in a simple list.

• addNumber: append to list.

• removeFirstAddedNumber: pop from front (O(n)).

• getMean: sum all elements (O(n)).

• getMedian: sort copy of list and pick middle (O(n log n)).

• getMode: count frequencies with a map and scan (O(n)).

This works but each operation may cost O(n) or O(n log n), leading to O(n²) over many calls.

Python Code