Welcome to Subscribe On Youtube
3092. Most Frequent IDs
Description
The problem involves tracking the frequency of IDs in a collection that changes over time. You have two integer arrays, nums
and freq
, of equal length n
. Each element in nums
represents an ID, and the corresponding element in freq
indicates how many times that ID should be added to or removed from the collection at each step.
 Addition of IDs: If
freq[i]
is positive, it meansfreq[i]
IDs with the valuenums[i]
are added to the collection at stepi
.  Removal of IDs: If
freq[i]
is negative, it meansfreq[i]
IDs with the valuenums[i]
are removed from the collection at stepi
.
Return an array ans
of length n
, where ans[i]
represents the count of the most frequent ID in the collection after the i^{th}
step. If the collection is empty at any step, ans[i]
should be 0 for that step.
Example 1:
Input: nums = [2,3,2,1], freq = [3,2,3,1]
Output: [3,3,2,2]
Explanation:
After step 0, we have 3 IDs with the value of 2. So ans[0] = 3
.
After step 1, we have 3 IDs with the value of 2 and 2 IDs with the value of 3. So ans[1] = 3
.
After step 2, we have 2 IDs with the value of 3. So ans[2] = 2
.
After step 3, we have 2 IDs with the value of 3 and 1 ID with the value of 1. So ans[3] = 2
.
Example 2:
Input: nums = [5,5,3], freq = [2,2,1]
Output: [2,0,1]
Explanation:
After step 0, we have 2 IDs with the value of 5. So ans[0] = 2
.
After step 1, there are no IDs. So ans[1] = 0
.
After step 2, we have 1 ID with the value of 3. So ans[2] = 1
.
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.
Solutions
Solution 1: Hash Table + Priority Queue (Max Heap)
We use a hash table $cnt$ to record the occurrence times of each ID, a hash table $lazy$ to record the number of times each occurrence needs to be deleted, and a priority queue $pq$ to maintain the maximum occurrence times.
For each operation $(x, f)$, we need to update the occurrence times $cnt[x]$ of $x$, which means the value of $cnt[x]$ in $lazy$ needs to increase by $1$, indicating that the number of times this occurrence needs to be deleted increases by $1$. Then we update the value of $cnt[x]$, adding $f$ to $cnt[x]$. Then we add the updated value of $cnt[x]$ to the priority queue $pq$. Then we check the top element of the priority queue $pq$. If the number of times the corresponding occurrence needs to be deleted in $lazy$ is greater than $0$, we pop the top element. Finally, we judge whether the priority queue is empty. If it is not empty, the top element is the maximum occurrence times, and we add it to the answer array.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $nums$.

class Solution { public long[] mostFrequentIDs(int[] nums, int[] freq) { Map<Integer, Long> cnt = new HashMap<>(); Map<Long, Integer> lazy = new HashMap<>(); int n = nums.length; long[] ans = new long[n]; PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder()); for (int i = 0; i < n; ++i) { int x = nums[i], f = freq[i]; lazy.merge(cnt.getOrDefault(x, 0L), 1, Integer::sum); cnt.merge(x, (long) f, Long::sum); pq.add(cnt.get(x)); while (!pq.isEmpty() && lazy.getOrDefault(pq.peek(), 0) > 0) { lazy.merge(pq.poll(), 1, Integer::sum); } ans[i] = pq.isEmpty() ? 0 : pq.peek(); } return ans; } }

class Solution { public: vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) { unordered_map<int, long long> cnt; unordered_map<long long, int> lazy; int n = nums.size(); vector<long long> ans(n); priority_queue<long long> pq; for (int i = 0; i < n; ++i) { int x = nums[i], f = freq[i]; lazy[cnt[x]]++; cnt[x] += f; pq.push(cnt[x]); while (!pq.empty() && lazy[pq.top()] > 0) { lazy[pq.top()]; pq.pop(); } ans[i] = pq.empty() ? 0 : pq.top(); } return ans; } };

class Solution: def mostFrequentIDs(self, nums: List[int], freq: List[int]) > List[int]: cnt = Counter() lazy = Counter() ans = [] pq = [] for x, f in zip(nums, freq): lazy[cnt[x]] += 1 cnt[x] += f heappush(pq, cnt[x]) while pq and lazy[pq[0]] > 0: lazy[pq[0]] = 1 heappop(pq) ans.append(0 if not pq else pq[0]) return ans

func mostFrequentIDs(nums []int, freq []int) []int64 { n := len(nums) cnt := map[int]int{} lazy := map[int]int{} ans := make([]int64, n) pq := hp{} heap.Init(&pq) for i, x := range nums { f := freq[i] lazy[cnt[x]]++ cnt[x] += f heap.Push(&pq, cnt[x]) for pq.Len() > 0 && lazy[pq.IntSlice[0]] > 0 { lazy[pq.IntSlice[0]] heap.Pop(&pq) } if pq.Len() > 0 { ans[i] = int64(pq.IntSlice[0]) } } return ans } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() any { a := h.IntSlice v := a[len(a)1] h.IntSlice = a[:len(a)1] return v }