# Most Frequent IDs **Difficulty:** MEDIUM [External](https://leetcode.com/problems/most-frequent-ids) Canonical: https://scaleengineer.com/dsa/problems/most-frequent-ids **Data structures:** Array, Hash Table, Heap (Priority Queue), Ordered Set --- ## Problem 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 means `freq[i]` IDs with the value `nums[i]` are added to the collection at step `i`. * **Removal of IDs:** If `freq[i]` is negative, it means `-freq[i]` IDs with the value `nums[i]` are removed from the collection at step `i`. Return an array `ans` of length `n`, where `ans[i]` represents the **count** of the _most frequent ID_ in the collection after the `ith` 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 <= 105` * `1 <= nums[i] <= 105` * `-105 <= freq[i] <= 105` * `freq[i] != 0` * The input is generated such that the occurrences of an ID will not be negative in any step. # Approaches ## Brute Force Simulation This approach directly simulates the process described in the problem. For each step, it updates the frequency of the current ID in a hash map. After the update, it performs a full scan of all the values in the hash map to find the current maximum frequency. This process is repeated for all `n` steps. **Time:** O(n^2), where `n` is the length of the arrays. For each of the `n` steps, we might iterate through up to `i` distinct ID counts in the map to find the maximum, leading to a total time of roughly Σ(i) from i=1 to n, which is O(n^2). · **Space:** O(D), where D is the number of distinct IDs in `nums`. In the worst case, D can be up to `n`, so the complexity is O(n). This is for storing the frequencies in the hash map and the result array. **Pros:** Easy to understand and implement.; Uses a standard hash map, a very common data structure. **Cons:** Highly inefficient for large inputs due to the nested loop structure.; Will result in a 'Time Limit Exceeded' error on platforms with strict time constraints. ### Explanation We use a hash map to maintain the frequency count of each ID. We iterate through the `nums` and `freq` arrays from left to right. In each step `i`, we update the frequency of `nums[i]` by adding `freq[i]` to its current count. After this update, we find the maximum frequency by iterating through all the values present in our hash map. This maximum value is the answer for step `i`. While simple, this method is slow because finding the maximum frequency requires a linear scan at every single step. ```java import java.util.HashMap; import java.util.Map; class Solution { public long[] mostFrequentIDs(int[] nums, int[] freq) { int n = nums.length; long[] ans = new long[n]; Map idCounts = new HashMap<>(); for (int i = 0; i < n; i++) { int id = nums[i]; long change = freq[i]; idCounts.put(id, idCounts.getOrDefault(id, 0L) + change); long maxFreq = 0; for (long count : idCounts.values()) { if (count > maxFreq) { maxFreq = count; } } ans[i] = maxFreq; } return ans; } } ``` ### Algorithm - 1. Initialize an empty hash map `idCounts` to store the frequency of each ID. - 2. Initialize an answer array `ans` of size `n`. - 3. Iterate from `i = 0` to `n-1`: - a. Update the count for `nums[i]` in `idCounts`. Since frequencies can be large, use `long` for the counts. `idCounts[nums[i]] = idCounts.getOrDefault(nums[i], 0L) + freq[i]`. - b. Initialize `maxFreq = 0`. - c. Iterate through all values in `idCounts`. For each `count`, update `maxFreq = max(maxFreq, count)`. - d. Set `ans[i] = maxFreq`. - 4. Return `ans`. ## Hash Map and Max-Heap (Priority Queue) To optimize finding the maximum frequency, this approach uses a max-heap (Priority Queue) in conjunction with a hash map. The hash map tracks the up-to-date frequency of each ID, while the max-heap is used to efficiently retrieve the highest frequency. **Time:** O(n log n). For each of the `n` steps, we perform one hash map update (O(1) on average) and one heap insertion (O(log n)). The cleanup loop also removes elements. Since each of the `n` updates is pushed to the heap once and popped at most once, the total time for all heap operations is O(n log n). · **Space:** O(n). In the worst case, the hash map and the max-heap can both store up to `n` entries. The heap might store multiple entries for the same ID before they are cleaned up. **Pros:** Significantly faster than the brute-force approach.; The O(n log n) time complexity is efficient enough for the given constraints. **Cons:** The max-heap can grow in size, storing stale entries that are only cleaned up when they reach the top, potentially using more memory than necessary at times.; Slightly more complex to implement than the brute-force approach. ### Explanation The core idea is to avoid the O(n) scan for the maximum frequency at each step. A max-heap can provide the maximum element in O(log k) time, where k is the heap size. We maintain a hash map `idCounts` for the true frequency of each ID and a max-heap `pq` storing `[frequency, ID]` pairs. At each step `i`, we update the frequency of `nums[i]` in `idCounts` and push the new `[frequency, ID]` pair into the heap. A problem arises: the heap may now contain old, incorrect frequency entries for that ID. For example, if an ID's frequency decreases, its old, higher frequency entry remains in the heap. We handle this by 'lazily' cleaning the heap. Before getting the max frequency, we check the top element of the heap. If its frequency doesn't match the one in our `idCounts` map, it's a stale entry, and we pop it. We repeat this until the top element is valid. The frequency of this valid top element is our answer for the current step. ```java import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; class Solution { public long[] mostFrequentIDs(int[] nums, int[] freq) { int n = nums.length; long[] ans = new long[n]; Map idCounts = new HashMap<>(); // Max-heap storing pairs of [frequency, id] PriorityQueue pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0])); for (int i = 0; i < n; i++) { int id = nums[i]; long change = freq[i]; long newCount = idCounts.getOrDefault(id, 0L) + change; idCounts.put(id, newCount); pq.offer(new long[]{newCount, (long)id}); // Remove stale entries from the top of the heap. while (!pq.isEmpty() && pq.peek()[0] != idCounts.get((int)pq.peek()[1])) { pq.poll(); } if (pq.isEmpty()) { ans[i] = 0; } else { ans[i] = pq.peek()[0]; } } return ans; } } ``` ### Algorithm - 1. Initialize an empty hash map `idCounts` to store `ID -> frequency`. - 2. Initialize an empty max-heap `pq` to store pairs `[frequency, ID]`. - 3. Initialize an answer array `ans` of size `n`. - 4. Iterate from `i = 0` to `n-1`: - a. Update the count for `nums[i]` in `idCounts`. - b. Add the new pair `[idCounts[nums[i]], nums[i]]` to `pq`. - c. The top of the heap might have a stale frequency. While `pq` is not empty and the frequency of the ID at the top of the heap does not match its current frequency in `idCounts`, remove the top element from `pq`. - d. If `pq` is empty, the max frequency is 0. Otherwise, it's the frequency of the top element: `pq.peek()[0]`. - e. Set `ans[i]` to this maximum frequency. - 5. Return `ans`. ## Two Maps (Hash Map + TreeMap) This is a highly efficient approach that uses two maps to solve the problem. The first map, a standard hash map, stores the frequency of each ID. The second map, a `TreeMap` (a balanced binary search tree), stores the counts of frequencies themselves. This structure allows us to find the maximum frequency in logarithmic time. **Time:** O(n log F), where `n` is the number of steps and `F` is the number of distinct frequencies present at any time. Since `F` can be at most `n`, the worst-case time complexity is O(n log n). Each step involves a few operations on the `TreeMap`, each taking O(log F) time. · **Space:** O(D), where D is the number of distinct IDs. Both the `idCounts` map and the `freqCounts` map can grow up to size D in the worst case. So the space complexity is O(D), which is O(n) in the worst case. **Pros:** Efficient O(n log n) time complexity.; Maintains a clean state without the 'stale' entries of the heap-based approach.; The number of elements in the TreeMap is bounded by the number of distinct frequencies, which can be smaller than the heap size in the previous approach. **Cons:** Operations on a balanced binary search tree (like TreeMap) can have higher constant factors than heap operations, though their asymptotic complexity is similar.; The logic involves managing two maps and can be slightly more complex to reason about than the heap approach. ### Explanation We maintain two data structures: a `HashMap idCounts` to track the frequency of each ID, and a `TreeMap freqCounts` to track how many IDs have a certain frequency. The `TreeMap` keeps its keys (the frequencies) in sorted order, which means we can find the maximum frequency (the last key) very quickly. For each step `i`: 1. We find the old frequency of `nums[i]`. We then decrement the count for this old frequency in our `freqCounts` map. If the count drops to zero, we remove that frequency entry entirely. 2. We calculate the new frequency for `nums[i]` and update it in `idCounts`. 3. We then increment the count for this new frequency in `freqCounts`. 4. The maximum frequency at this step is simply the largest key in the `freqCounts` `TreeMap`. If the `TreeMap` is empty (meaning all IDs have a frequency of 0), the answer is 0. This method avoids the issue of stale entries seen in the heap approach, as the state of `freqCounts` is always perfectly consistent with `idCounts`. ```java import java.util.HashMap; import java.util.Map; import java.util.TreeMap; class Solution { public long[] mostFrequentIDs(int[] nums, int[] freq) { int n = nums.length; long[] ans = new long[n]; Map idCounts = new HashMap<>(); // Key: frequency, Value: number of IDs with this frequency TreeMap freqCounts = new TreeMap<>(); for (int i = 0; i < n; i++) { int id = nums[i]; long change = freq[i]; // Get old frequency and update freqCounts long oldFreq = idCounts.getOrDefault(id, 0L); if (oldFreq > 0) { freqCounts.put(oldFreq, freqCounts.get(oldFreq) - 1); if (freqCounts.get(oldFreq) == 0) { freqCounts.remove(oldFreq); } } // Calculate new frequency and update both maps long newFreq = oldFreq + change; idCounts.put(id, newFreq); if (newFreq > 0) { freqCounts.put(newFreq, freqCounts.getOrDefault(newFreq, 0) + 1); } // The max frequency is the last key in the TreeMap if (freqCounts.isEmpty()) { ans[i] = 0; } else { ans[i] = freqCounts.lastKey(); } } return ans; } } ``` ### Algorithm - 1. Initialize a hash map `idCounts` to store `ID -> frequency`. - 2. Initialize a `TreeMap` `freqCounts` to store `frequency -> count of IDs with this frequency`. - 3. Initialize an answer array `ans` of size `n`. - 4. Iterate from `i = 0` to `n-1`: - a. Get the `id` and `change` in frequency. - b. Find the `oldFreq` of the `id` from `idCounts`. - c. If `oldFreq > 0`, decrement its count in `freqCounts`. If the count becomes zero, remove the `oldFreq` key. - d. Calculate `newFreq = oldFreq + change`. - e. Update the `id`'s frequency in `idCounts` to `newFreq`. - f. If `newFreq > 0`, increment its count in `freqCounts`. - g. The maximum frequency is the largest key in `freqCounts`. If the `TreeMap` is empty, the max frequency is 0. Otherwise, it's `freqCounts.lastKey()`. - h. Store this max frequency in `ans[i]`. - 5. Return `ans`. # Solutions ### Java ```java class Solution { public long[] mostFrequentIDs(int[] nums, int[] freq) { Map cnt = new HashMap<>(); Map lazy = new HashMap<>(); int n = nums.length; long[] ans = new long[n]; PriorityQueue 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; } } ``` ### CPP ```cpp class Solution { public: vector mostFrequentIDs(vector &nums, vector &freq) { unordered_map cnt; unordered_map lazy; int n = nums.size(); vector ans(n); priority_queue 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; } }; ``` ### Python ```python 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 ```