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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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.

Solution

Method 1 - Hash Map + TreeMap (Java) / SortedDict (Python)

Intuition

We need to efficiently track the frequency of each ID and quickly find the maximum frequency after each step. We use a hash map for ID counts and a TreeMap (Java) or SortedDict (Python) for frequency counts.

Approach

For each step:

  1. Update the count for the current ID (add or remove).
  2. Update the frequency map: decrement the old frequency, increment the new frequency.
  3. The maximum frequency is the largest key in the frequency map (or 0 if empty).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int[] mostFrequentIDs(int[] nums, int[] freq) {
        int n = nums.length;
        int[] ans = new int[n];
        Map<Integer, Integer> count = new HashMap<>();
        TreeMap<Integer, Integer> freqMap = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int id = nums[i], f = freq[i];
            int old = count.getOrDefault(id, 0);
            int now = old + f;
            count.put(id, now);
            if (old > 0) {
                freqMap.put(old, freqMap.get(old) - 1);
                if (freqMap.get(old) == 0) freqMap.remove(old);
            }
            freqMap.put(now, freqMap.getOrDefault(now, 0) + 1);
            ans[i] = freqMap.isEmpty() ? 0 : freqMap.lastKey();
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def mostFrequentIDs(nums, freq):
    from collections import defaultdict
    from sortedcontainers import SortedDict
    count = defaultdict(int)
    freq_map = SortedDict()
    ans = []
    for id, f in zip(nums, freq):
        old = count[id]
        now = old + f
        count[id] = now
        if old > 0:
            freq_map[old] -= 1
            if freq_map[old] == 0:
                del freq_map[old]
        freq_map[now] = freq_map.get(now, 0) + 1
        ans.append(freq_map.peekitem(-1)[0] if freq_map else 0)
    return ans

Complexity

  • ⏰ Time complexity: O(n log n) — Each step involves log n operations for TreeMap/SortedDict.
  • 🧺 Space complexity: O(n) — For count and frequency maps.