Most Frequent IDs

Med

#2746Time: 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.

Data structures

Array Hash Table Heap (Priority Queue)Ordered Set

Prompt

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 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⁵
1 <= nums[i] <= 10⁵
-10⁵ <= freq[i] <= 10⁵
freq[i] != 0
The input is generated such that the occurrences of an ID will not be negative in any step.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Initialize an empty hash map idCounts to store the frequency of each ID.
1. Initialize an answer array ans of size n.
1. 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.
1. Return ans.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long[] mostFrequentIDs(int[] nums, int[] freq) {6        int n = nums.length;7        long[] ans = new long[n];8        Map<Integer, Long> idCounts = new HashMap<>();9 10        for (int i = 0; i < n; i++) {11            int id = nums[i];12            long change = freq[i];13            14            idCounts.put(id, idCounts.getOrDefault(id, 0L) + change);15            16            long maxFreq = 0;17            for (long count : idCounts.values()) {18                if (count > maxFreq) {19                    maxFreq = count;20                }21            }22            ans[i] = maxFreq;23        }24        25        return ans;26    }27}

Complexity

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.

Trade-offs

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.

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.

Algorithm

1. Initialize an empty hash map idCounts to store ID -> frequency.
1. Initialize an empty max-heap pq to store pairs [frequency, ID].
1. Initialize an answer array ans of size n.
1. 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.
1. Return ans.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3import java.util.PriorityQueue;4 5class Solution {6    public long[] mostFrequentIDs(int[] nums, int[] freq) {7        int n = nums.length;8        long[] ans = new long[n];9        Map<Integer, Long> idCounts = new HashMap<>();10        // Max-heap storing pairs of [frequency, id]11        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));12 13        for (int i = 0; i < n; i++) {14            int id = nums[i];15            long change = freq[i];16            17            long newCount = idCounts.getOrDefault(id, 0L) + change;18            idCounts.put(id, newCount);19            20            pq.offer(new long[]{newCount, (long)id});21            22            // Remove stale entries from the top of the heap.23            while (!pq.isEmpty() && pq.peek()[0] != idCounts.get((int)pq.peek()[1])) {24                pq.poll();25            }26            27            if (pq.isEmpty()) {28                ans[i] = 0;29            } else {30                ans[i] = pq.peek()[0];31            }32        }33        34        return ans;35    }36}

Complexity

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.

Trade-offs

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.

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.

Algorithm

1. Initialize a hash map idCounts to store ID -> frequency.
1. Initialize a TreeMap freqCounts to store frequency -> count of IDs with this frequency.
1. Initialize an answer array ans of size n.
1. 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].
1. Return ans.

Walkthrough

We maintain two data structures: a HashMap<Integer, Long> idCounts to track the frequency of each ID, and a TreeMap<Long, Integer> 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:

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.
We calculate the new frequency for nums[i] and update it in idCounts.
We then increment the count for this new frequency in freqCounts.
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.

1import java.util.HashMap;2import java.util.Map;3import java.util.TreeMap;4 5class Solution {6    public long[] mostFrequentIDs(int[] nums, int[] freq) {7        int n = nums.length;8        long[] ans = new long[n];9        Map<Integer, Long> idCounts = new HashMap<>();10        // Key: frequency, Value: number of IDs with this frequency11        TreeMap<Long, Integer> freqCounts = new TreeMap<>();12 13        for (int i = 0; i < n; i++) {14            int id = nums[i];15            long change = freq[i];16            17            // Get old frequency and update freqCounts18            long oldFreq = idCounts.getOrDefault(id, 0L);19            if (oldFreq > 0) {20                freqCounts.put(oldFreq, freqCounts.get(oldFreq) - 1);21                if (freqCounts.get(oldFreq) == 0) {22                    freqCounts.remove(oldFreq);23                }24            }25            26            // Calculate new frequency and update both maps27            long newFreq = oldFreq + change;28            idCounts.put(id, newFreq);29            if (newFreq > 0) {30                freqCounts.put(newFreq, freqCounts.getOrDefault(newFreq, 0) + 1);31            }32            33            // The max frequency is the last key in the TreeMap34            if (freqCounts.isEmpty()) {35                ans[i] = 0;36            } else {37                ans[i] = freqCounts.lastKey();38            }39        }40        41        return ans;42    }43}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  long[] mostFrequentIDs(int[] nums, int[] freq) {4    Map<Integer, Long> cnt = new HashMap<>();5    Map<Long, Integer> lazy = new HashMap<>();6    int n = nums.length;7    long[] ans = new long[n];8    PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());9    for (int i = 0; i < n; ++i) {10      int x = nums[i], f = freq[i];11      lazy.merge(cnt.getOrDefault(x, 0L), 1, Integer : : sum);12      cnt.merge(x, (long)f, Long : : sum);13      pq.add(cnt.get(x));14      while (!pq.isEmpty() && lazy.getOrDefault(pq.peek(), 0) > 0) {15        lazy.merge(pq.poll(), -1, Integer : : sum);16      }17      ans[i] = pq.isEmpty() ? 0 : pq.peek();18    }19    return ans;20  }21}

1class Solution {2public:3  vector<long long> mostFrequentIDs(vector<int> &nums, vector<int> &freq) {4    unordered_map<int, long long> cnt;5    unordered_map<long long, int> lazy;6    int n = nums.size();7    vector<long long> ans(n);8    priority_queue<long long> pq;9    for (int i = 0; i < n; ++i) {10      int x = nums[i], f = freq[i];11      lazy[cnt[x]]++;12      cnt[x] += f;13      pq.push(cnt[x]);14      while (!pq.empty() && lazy[pq.top()] > 0) {15        lazy[pq.top()]--;16        pq.pop();17      }18      ans[i] = pq.empty() ? 0 : pq.top();19    }20    return ans;21  }22};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  long[] mostFrequentIDs(int[] nums, int[] freq) {4    Map<Integer, Long> cnt = new HashMap<>();5    Map<Long, Integer> lazy = new HashMap<>();6    int n = nums.length;7    long[] ans = new long[n];8    PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());9    for (int i = 0; i < n; ++i) {10      int x = nums[i], f = freq[i];11      lazy.merge(cnt.getOrDefault(x, 0L), 1, Integer : : sum);12      cnt.merge(x, (long)f, Long : : sum);13      pq.add(cnt.get(x));14      while (!pq.isEmpty() && lazy.getOrDefault(pq.peek(), 0) > 0) {15        lazy.merge(pq.poll(), -1, Integer : : sum);16      }17      ans[i] = pq.isEmpty() ? 0 : pq.peek();18    }19    return ans;20  }21}

1class Solution {2public:3  vector<long long> mostFrequentIDs(vector<int> &nums, vector<int> &freq) {4    unordered_map<int, long long> cnt;5    unordered_map<long long, int> lazy;6    int n = nums.size();7    vector<long long> ans(n);8    priority_queue<long long> pq;9    for (int i = 0; i < n; ++i) {10      int x = nums[i], f = freq[i];11      lazy[cnt[x]]++;12      cnt[x] += f;13      pq.push(cnt[x]);14      while (!pq.empty() && lazy[pq.top()] > 0) {15        lazy[pq.top()]--;16        pq.pop();17      }18      ans[i] = pq.empty() ? 0 : pq.top();19    }20    return ans;21  }22};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.