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)

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

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

To support removal of the earliest added element, think of a queue.
For median queries, what data structure lets you insert, delete, and find the middle element efficiently?
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

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Each operation: up to O(n log n)
Not suitable when total calls ≫ n.

Approach 2 Optimized with Balanced Structures

Explanation

Maintain:

A queue for removal of the earliest element.
A running sum for O(1) mean.
A balanced tree (or SortedList in Python / TreeMap in Java) to insert/delete in O(log n) and find the k‑th element for median.
A frequency map + max‑heap for mode, using lazy removal of stale heap entries.

Step‑by‑Step Walkthrough

addNumber(x):
- enqueue x, add to sum.
- insert x into sorted structure.
- increment count[x], push (−count[x], x) into max‑heap.
removeFirstAddedNumber():
- dequeue old, subtract from sum.
- remove one occurrence of old from sorted structure.
- decrement count[old] (remove key if zero).
getMean(): return sum // size.
getMedian(): let k = size//2. Return the element at index k in the sorted structure (0‑based).
getMode():
- Peek top of heap (−f, x).
- If count[x] == f, return x.
- Else pop and repeat (lazy cleanup).

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

addNumber / removeFirstAddedNumber: O(log n) for tree operations and heap push.
getMean: O(1)
getMedian: O(log n) to locate median in a tree, or O(1) with a SortedList that supports index.
getMode: Amortized O(1) for peek + occasional O(log n) for stale‐entry pops.
Space: O(n)

Common Mistakes

Not handling even‑sized median correctly (must pick the larger middle).
Forgetting to clean up stale entries in the mode heap, leading to wrong answers.
Removing from the wrong end (must remove the first added).