Most Frequent IDs
01 · Problem
You maintain a collection of IDs that starts out empty. You are given two arrays nums and freq of equal length n. At step i:
- if
freq[i] > 0, addfreq[i]copies of IDnums[i]to the collection; - if
freq[i] < 0, remove-freq[i]copies of IDnums[i]from the collection.
It is guaranteed that a removal never takes the count of an ID below zero.
Return an array ans of length n where ans[i] is the count of the most frequent ID in the collection right after step i. If the collection is empty after a step, ans[i] is 0.
02 · Examples
nums = [2,3,2,1], freq = [3,2,-3,1]
[3,3,2,2]
After step 0: {2:3} -> 3. After step 1: {2:3, 3:2} -> 3. After step 2: {2:0, 3:2} -> 2. After step 3: {3:2, 1:1} -> 2.
nums = [5,5,3], freq = [2,-2,1]
[2,0,1]
After step 0 ID 5 appears twice -> 2. Step 1 removes both copies, leaving the collection empty -> 0. Step 2 adds one copy of 3 -> 1.
nums = [7], freq = [4]
[4]
A single step adds four copies of ID 7, so the answer is 4.
03 · Constraints
- 011 <= nums.length == freq.length <= 105
- 021 <= nums[i] <= 105
- 03-105 <= freq[i] <= 105
- 04freq[i] != 0
- 05The count of any ID never becomes negative
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.