MediumArrayHash TableHeapOrdered SetUpdated Sep 2026

3092. Most Frequent IDs

Asked at Snowflake

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given two integer arrays nums and freq, both of length n. Together they describe a sequence of updates to a collection of IDs. At step i, the ID nums[i] is added freq[i] times if freq[i] is positive, or removed -freq[i] times if freq[i] is negative. The collection can hold many copies of the same ID.

After each step, you must know the count of the most frequent ID in the collection — that is, the largest number of copies any single ID currently has. Return an array ans of length n, where ans[i] is that maximum after step i.

If the collection is empty after a step, the answer for that step is 0. The input guarantees that you never remove more copies of an ID than currently exist, so counts never go negative.

Track the top count after each update

nums23210123step 0IDs touched at each stepfreq32-310123Positive adds copies, negative removes themans33220123After step 0 the max is 3; after step 2 it drops to 2
Each step changes one ID's count; we report the largest count in the collection right after that change.

Constraints

  • ●1 <= nums.length == freq.length <= 10^5
  • ●1 <= nums[i] <= 10^5
  • ●-10^5 <= freq[i] <= 10^5
  • ●freq[i] != 0
  • ●The input is generated such that the occurrences of an ID will not be negative in any step.

Examples

Example 1
Inputnums = [2,3,2,1], freq = [3,2,-3,1]
Output[3,3,2,2]
WhyStep 0 adds 3 copies of ID 2, so the max is 3. Step 1 adds 2 copies of ID 3; ID 2 still has 3, so the max stays 3. Step 2 removes 3 copies of ID 2, leaving only ID 3 with 2 copies, so the max drops to 2. Step 3 adds 1 copy of ID 1; ID 3 still leads with 2, so the max stays 2.
Example 2
Inputnums = [5,5,3], freq = [2,-2,1]
Output[2,0,1]
WhyStep 0 adds 2 copies of ID 5, so the max is 2. Step 1 removes those 2 copies, so the collection is empty and the answer is 0. Step 2 adds 1 copy of ID 3, so the max is 1.

Asked At

1 companies
CompanyDifficulty
SnowflakeMediumView all Snowflake questions →

How to Think About It

1

Keep a hash map count[id]. Scanning it for the maximum after every step is O(n) per step.

2

Key insight: push (count, id) onto a max-heap every time an ID's count changes. Old entries become stale, but you can detect them: an entry is valid only if its count equals the current count[id].

3

After each update, pop stale entries from the top until the top is valid (or the heap is empty). The top is then the answer.

4

Ordered-set alternative: maintain a multiset (or a map from count to how many IDs have it) and read its largest key.

5

Counts can reach 10^5 * 10^5 = 10^10, so use 64-bit integers.

Optimal Approach

Step 1: count = {}, heap = [], res = [].
Step 2: For each (id, delta):
count[id] += delta; push (-count[id], id).
While the top (c, i) has -c != count[i]: pop.
Append -heap[0][0] if the heap is non-empty, else 0.
Step 3: Return res.

Time: O(n log n). Space: O(n).

Hash map plus lazy max-heap

countafter step 1after step 3233211The map holds the live count for each IDmax-heap (top first)(3,2)(2,3)(1,1)← topThe top entry (3,2) matches count[2]=3, so the answeris 3push (-count[id], id)pop while -top.count != count[top.id]answer = top count, or 0 if empty
Push every new count onto a max-heap, then discard the top while it disagrees with the map.
ComplexityTime O(n log n)Space O(n)Each step does one heap push and possibly some pops, and every stale entry is popped at most once, so the total work is bounded by n log n.

What Trips People Up in Real Interviews

1

Scanning all IDs after each update — O(n²) overall.

2

Trying to update or remove entries inside a heap directly. Lazy deletion avoids it.

3

Returning the ID instead of its count.

4

Overflow in C++/Java; the answer array is long.

Solution Code

O(n log n) time
import heapq

def mostFrequentIDs(nums, freq):
    count = {}
    heap = []
    res = []
    for x, f in zip(nums, freq):
        count[x] = count.get(x, 0) + f
        heapq.heappush(heap, (-count[x], x))
        while heap and -heap[0][0] != count[heap[0][1]]:
            heapq.heappop(heap)
        res.append(-heap[0][0] if heap else 0)
    return res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Most Frequent IDs problem?

Most Frequent IDs processes a stream of updates `(id, delta)` that add or remove copies of an ID, and after each update asks for the count of the most frequent ID (0 if the collection is empty). You need a structure that returns a maximum while counts go up and down — a max-heap with lazy deletion, or an ordered multiset of counts.

How do you solve Most Frequent IDs?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Most Frequent IDs?

Most Frequent IDs is asked at Snowflake. It is a medium difficulty problem.

What are common mistakes on Most Frequent IDs?
  • Scanning all IDs after each update — `O(n²)` overall.
  • Trying to update or remove entries inside a heap directly. Lazy deletion avoids it.
  • Returning the ID instead of its count.
  • Overflow in C++/Java; the answer array is `long`.