Abstract / Summary

Given a stream of integers and two values m and k, find the mth largest element among the last k elements for each query.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 37% (50k+ submissions).

Typical patterns to solve this problem:

• Data Stream
• Design
• Heap (Priority Queue)
• Ordered Set
• Queue

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The class implements a sliding-window statistical aggregator known as MKAverage. It maintains the most recent m elements, discards the smallest k and the largest k values, and returns the integer average of the remaining m-2k numbers. The implementation relies on a double-ended queue to store the raw sequence and an ordered map to keep a frequency count of each distinct value currently in the window.

Core Data Structures

The window is represented by a deque<int> named data. New elements are appended at the back, and when the window exceeds its configured size m, the oldest element is removed from the front. The ordered map freq (map<int,int>) stores how many times each value appears in the current window. Because map keeps its keys sorted, iterating over freq yields the values in ascending order, which is essential for efficiently skipping the smallest and largest k elements without additional sorting.

Construction

MKAverage(int m, int k)
: data(),
  freq(),
  size(m),
  ignore(k)
{ }

The constructor records the window size size and the number of elements to ignore on each side ignore. No allocation is performed beyond the default construction of the container members.

Adding an Element

void addElement(int num)
{
    data.push_back(num);
    freq[num]++;
    if (data.size() > size)
    {
        freq[data.front()]--; // optional: delete this entry if zero
        data.pop_front();
    }
}

When a new integer arrives, it is pushed onto data and its count is incremented in freq. If the window now contains more than size elements, the element at the front of the deque (the oldest) is removed and its frequency is decremented. The comment notes that an entry whose count drops to zero could be erased, but the code leaves it in place, which simplifies the logic of later traversal.

Edge Cases Handled

• Adding elements before the window reaches full capacity does not trigger removal, preserving all inputs.
• When the oldest element’s frequency becomes zero, the map still holds a key with a zero count; this does not affect later calculations because the iteration logic checks the count against the number of elements to skip.

Calculating the MKAverage

int calculateMKAverage()
{
    if (data.size() < size)
        return -1;

    int64_t sum = 0;
    int skip = ignore;
    int have = 0;
    int need = size - 2*ignore;
    for (auto i : freq)
    {
        // ignore this number
        if (i.second <= skip)
        {
            skip -= i.second;
            continue;
        }

        int take = i.second;
        // take only partial (left side)
        if (skip > 0)
        {
            take -= skip;
            skip  = 0;
        }
        // take only partial (right side)
        take = min(take, need - have);

        sum  += take * i.first;
        have += take;
        if (have == need)
            break;
    }

    return sum / need;
}

The method first checks whether the window is fully populated; if not, it returns -1 as a sentinel value. The variables skip, have, and need control the traversal:

• skip tracks how many of the smallest elements still need to be omitted.
• have counts how many elements have already been included in the sum.
• need is the exact number of elements that must contribute to the average (m-2k).

The loop iterates over the ordered map entries. For each distinct value i.first with frequency i.second:

1. If the entire frequency can be consumed by the remaining skip, the code reduces skip accordingly and proceeds to the next entry.
2. Otherwise, it computes how many of the current value can be taken after satisfying any leftover skip. This may involve taking a partial count when the current frequency exceeds the remaining skip.
3. The take count is then limited to the remaining slots needed to reach need. This ensures that the algorithm stops exactly after gathering the required number of middle elements.
4. The contribution to sum is accumulated using a 64-bit integer to avoid overflow when multiplying take by the value.
5. When have reaches need, the loop exits early, avoiding unnecessary traversal of larger values.

Edge Cases Handled

• When the smallest values collectively exceed k, the algorithm correctly reduces skip across multiple map entries.
• When a frequency straddles the boundary between ignored and kept elements, the partial-take logic captures only the portion that belongs to the middle segment.
• When the largest values are reached before need elements have been collected, the min operation ensures that the algorithm never exceeds the required count.
• The early break prevents processing of values beyond the required middle segment, which is crucial when the map contains many distinct keys.

Performance Optimizations

The design leverages several implicit optimizations:

• Amortized O(1) insertion and removal: The deque provides constant-time push-back and pop-front operations, keeping the sliding window update cheap regardless of its size.
• Ordered frequency map: By using map, the code avoids sorting the window on each query. The map maintains keys in ascending order, allowing a single linear pass over distinct values to locate the middle segment.
• Early termination of the aggregation loop: The if (have == need) break; statement stops the iteration as soon as the required number of elements has been summed, which can be a substantial saving when the distribution of values is skewed toward the extremes.
• Avoiding unnecessary deletions: The comment in addElement mentions that entries with zero count could be erased, but the code deliberately leaves them. This avoids the overhead of map node removal and rebalancing during each slide operation.
• 64-bit accumulation: Using int64_t for sum prevents overflow without requiring additional checks, allowing the multiplication take * i.first to be performed safely in a single instruction on most platforms.

These choices collectively keep the per-operation cost low, especially when the window size m is large but the number of distinct values remains moderate. The algorithm scales well with the number of unique elements rather than the total number of elements in the window.

Imagine having a long toy train that can only hold a certain number of cars at one time. Every time you get a new car, you add it to the back of the train. If the train gets too full, you take the oldest car off the front so there is always room for the new one. This keeps the train exactly the size you want.

Inside the train, you keep a list of how many of each car you have, like having three red cars and two blue cars. When it is time to figure out the average, you look at all the cars you have currently. To make the average fair, you throw away some of the smallest cars and some of the largest cars. You have a special set of rules for how many to ignore on each end. After tossing those aside, you add up the values of all the cars that are left in the middle. You divide that total by the number of remaining cars to find the final result. If the train does not have enough cars yet to play the game, you just wait for more to arrive.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++			Java
	leetcode.ca	C++		Python	Java		Go
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality