Solution to Leetcode 3092: Most Frequent IDs

In this exercise, we are tracking the frequencies of some IDs, and need to return the ID with max frequency after each operation.

Collection interface

As is explained in the exercise, we essentially need to build a data structure that supports the 3 following operation:

• Retrieve the most frequent ID
• Increase the frequency of an ID
• Decrease the frequency of an ID

This gives us our base interface:

interface IDFrequencies {
    // ID with max frequency
    public long maxFreq();
    // Increase "id" frequency by "freq"
    public void add(int id, long freq);
    // Decrease "id" frequency by "freq"
    public void remove(int id, long freq);
}

I’ll add a little caveat here, it wasn’t very clear for me from the exercise if we needed to actually support increase and decrease instead of just adding and removing values from the collection, in which case we could have used a Sorted Map. In any case, my solution will work.

Collection implementation

Since the implementation is a little long, I won’t go into every minute detail on how I implemented it and will keep it at a high level. First I didn’t see any obvious Java collection that could do the job, which is why I am implementing my own. Since we need to retrieve the max frequency, I used a max queue backed by an array: