Skip to main content

Heaps

Most Frequent IDs Problem Solution In C++/Java/Python/Javascript

Problem 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 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

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.

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.
💡
Try it Yourself
We are given two arrays: one with IDs and another with operations (add or remove counts for each ID). At each step, we update the collection by adding or removing the specified number of the given ID. The main idea lies in how to determine frequency for each creator dynamically.

Brute Force Approach

Intuition

Most Frequent IDs example in real life can be thought as Imagine you have a basket that holds different types of fruits. Each time you receive an instruction, you either add a certain number of one type of fruit or remove some from the basket. The goal is to know which fruit you have the most of after each instruction. This is similar to the problem where you have two arrays—one for IDs (which represent different fruits) and another for frequencies (which tell you how many to add or remove). The task is to track the frequency of each ID (or fruit) and determine the maximum frequency after every operation.

In real life if we want to track the frequency we maintains a register where the key is recorded and as according to flow we update the value of key by the frequency.
Now in coding terms the main question is what data structure can we maintain which would fulfil the work the register does in real life. This is when the hash map comes into play.

What is a hash map?

A hash map (or hash table) is a data structure that stores key-value pairs, providing an efficient way to insert, delete, and retrieve data. It uses a hash function to compute an index from the given key, allowing for fast access to values. The computed index determines the position in an array where the corresponding key-value pair is stored. This structure is widely used in applications that require fast lookups, such as caching, database indexing, and symbol tables in compilers.

The efficiency of a hash map comes from its average-case time complexity of O(1)for insertion, deletion, and lookup operations. This is achieved when the hash function distributes keys evenly across the table, minimizing collisions. However, in the worst case, when multiple keys map to the same index, operations can degrade to O(n), as resolving collisions requires additional steps. Common collision resolution techniques include chaining, where each index stores a linked list of entries, and open addressing, where probing is used to find the next available slot in the array.

The space complexity of a hash map is O(n), where n is the number of elements stored. The efficiency of storage depends on the load factor, which measures the ratio of stored elements to the table’s size. If this factor exceeds a certain threshold (commonly 0.75), the table resizes itself, usually by doubling its capacity. This resizing ensures performance remains close to O(1), but it temporarily increases the cost of operations due to rehashing all elements.

Despite its advantages, a hash map has some drawbacks. The occurrence of collisions can degrade performance, requiring extra memory for linked lists or empty slots. Additionally, the unordered nature of hash maps makes them unsuitable for scenarios where maintaining the insertion order is essential. However, with proper implementation and a well-designed hash function, hash maps remain one of the most powerful and widely used data structures for fast key-based lookups.


The brute force technique starts with creating a simple container, like a hash map, to keep track of the count of each fruit. For every instruction, you update the hash map: if the frequency is positive, you add that many fruits; if it’s negative, you remove them. Once the update is done, you go through the hash map to find out which fruit has the highest count. This scanning through the entire hash map to get the maximum frequency is the key step that makes this approach straightforward but less efficient if you have many unique fruits or operations.

For instance, suppose in the first step you add 3 apples. Your hash map now records 3 apples, so the most frequent fruit is apples with a count of 3. In the next step, if you add 2 oranges, you update the hash map to have 3 apples and 2 oranges, and the maximum remains 3. Later, if you remove 3 apples, the hash map will update accordingly, perhaps leaving you with only oranges, and you then identify that oranges are now the most frequent. After each operation, you repeat the scanning process to determine the new maximum count.

Approach

Step 1: Initialize Frequency hash map
Create an empty hash map to store the current count for each unique ID. This hash map will be updated as you process each operation.

Step 2: Process Each Operation
For each index in the arrays, retrieve the corresponding ID from nums and the operation value from freq.

  • If the operation value is positive, add that many instances of the ID to the hash map by increasing its count.
  • If the operation value is negative, subtract the corresponding number (using its absolute value) from the ID's count, ensuring that the count does not go below zero.

Step 3: Determine Maximum Frequency
After updating the hash map for the current operation, scan through all the counts in the hash map to find the highest count. If the Hash Table is empty or all counts are zero, consider the maximum frequency for that step as zero.

Step 4: Record the Result
Append the maximum frequency found in the previous step to an answer list. This list keeps track of the maximum frequency after each operation.

Step 5: Return the Final Answer
Once all operations have been processed, return the answer list. This list contains the maximum frequency of any ID after each step in the order the operations were applied.

Dry Run Most Frequent IDs Algorithm's Dry Run is as follows:

Given Input:

  • nums = [2, 3, 2, 1]
  • freq = [3, 2, -3, 1]

Initial State:

  • Start with an empty Hash Table to track the frequency of each ID.
  • The answer list is empty at the beginning.

Step 1: Process First Operation

  • The first ID is 2, and the frequency change is +3.
  • Add 3 instances of ID 2 to the collection.
  • The Hash Table becomes {2: 3}.
  • The maximum frequency is 3 (since ID 2 appears 3 times).
  • Append 3 to the answer list.

Current Answer List: [3]

Step 2: Process Second Operation

  • The next ID is 3, and the frequency change is +2.
  • Add 2 instances of ID 3 to the collection.
  • The Hash Table updates to {2: 3, 3: 2}.
  • The maximum frequency remains 3 (since ID 2 appears 3 times, which is more than ID 3’s 2 times).
  • Append 3 to the answer list.

Current Answer List: [3, 3]

Step 3: Process Third Operation

  • The next ID is 2, and the frequency change is -3.
  • Remove 3 instances of ID 2 from the collection.
  • The Hash Table updates to {3: 2} (ID 2 is completely removed).
  • The maximum frequency is now 2 (since ID 3 appears twice).
  • Append 2 to the answer list.

Current Answer List: [3, 3, 2]

Step 4: Process Fourth Operation

  • The next ID is 1, and the frequency change is +1.
  • Add 1 instance of ID 1 to the collection.
  • The Hash Table updates to {3: 2, 1: 1}.
  • The maximum frequency remains 2 (since ID 3 appears twice, while ID 1 appears once).
  • Append 2 to the answer list.

Current Answer List: [3, 3, 2, 2]

Final Output:

[3, 3, 2, 2]

Code for All Languages
Most Frequent IDs solution in C++ :Brute Force 
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
        unordered_map<int, long long> count_map;  // Stores frequency of each ID
        vector<long long> ans;  // Stores the max frequency after each step
        
        for (int i = 0; i < nums.size(); i++) {
            count_map[nums[i]] += freq[i];  // Update frequency
            
            if (count_map[nums[i]] == 0) { 
                count_map.erase(nums[i]);  // Remove ID if count becomes zero
            }

            // Find the maximum frequency
            long long maxFreq = 0;
            for (const auto& entry : count_map) {
                maxFreq = max(maxFreq, entry.second);
            }

            ans.push_back(maxFreq);  // Store result
        }
        
        return ans;
    }
};

Most Frequent IDs solution in Java :Brute Force 
import java.util.*;

class Solution {
    public List<Long> mostFrequentIDs(int[] nums, int[] freq) {
        Map<Integer, Long> countMap = new HashMap<>(); // Stores frequency of each ID
        List<Long> ans = new ArrayList<>(); // Stores max frequency after each step

        for (int i = 0; i < nums.length; i++) {
            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0L) + freq[i]); // Update frequency

            if (countMap.get(nums[i]) == 0) {
                countMap.remove(nums[i]); // Remove ID if count becomes zero
            }

            // Find the maximum frequency
            long maxFreq = 0;
            for (long value : countMap.values()) {
                maxFreq = Math.max(maxFreq, value);
            }

            ans.add(maxFreq); // Store result
        }

        return ans;
    }
}

Most Frequent IDs solution in Python :Brute Force 
from typing import List

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        count_map = {}  # Dictionary to store frequency of each ID
        ans = []  # Stores max frequency after each step

        for i in range(len(nums)):
            count_map[nums[i]] = count_map.get(nums[i], 0) + freq[i]  # Update frequency
            
            if count_map[nums[i]] == 0:
                del count_map[nums[i]]  # Remove ID if count becomes zero

            # Find the maximum frequency
            max_freq = max(count_map.values(), default=0)

            ans.append(max_freq)  # Store result

        return ans

Most Frequent IDs solution in Javascript :Brute Force 
var mostFrequentIDs = function(nums, freq) {
    let countMap = new Map();  // Map to store frequency of each ID
    let ans = [];  // Stores max frequency after each step

    for (let i = 0; i < nums.length; i++) {
        countMap.set(nums[i], (countMap.get(nums[i]) || 0) + freq[i]);  // Update frequency

        if (countMap.get(nums[i]) === 0) {
            countMap.delete(nums[i]);  // Remove ID if count becomes zero
        }

        // Find the maximum frequency
        let maxFreq = Math.max(0, ...countMap.values());

        ans.push(maxFreq);  // Store result
    }

    return ans;
};

Most Frequent IDs complexity analysis:Time Complexity O(n^2).

Step 1: Initializing the Frequency Hash Table : O(1)

a) We create an empty Hash Table to store the count of each ID.
b) This operation takes O(1) time.

Step 2: Processing Each Operation : O(n)

Updating the Frequency Hash Table

a) If freq[i] > 0, we increase the count of nums[i] by freq[i].
b) If freq[i] < 0, we decrease the count of nums[i] by |freq[i]|.
c) Hash Table operations (insertion, update, and deletion) are O(1) on average.
d) Over n iterations, this step contributes O(n) in total.


Finding the Maximum Frequency : O(n²)

a) After updating the Hash Table, we scan through all values to find the maximum frequency.
b) If there are m unique IDs in the Hash Table at any step, scanning takes O(m) time.
c) In the worst case, all n elements are unique, making m = n.
d) This means scanning the Hash Table takes O(n) time per iteration.
e) Over n iterations, this step contributes O(n²) in total.

Step 3: Appending the Result : O(n)

a) Appending a value to the result list takes O(1) time per step.
b) Over n steps, this contributes O(n) in total.

Most Frequent IDs complexity analysis: Space Complexity O(n ).

1] Input Space Complexity : O(n)

a) The input consists of two arrays, nums and freq, each of length n.
b) These arrays are given as input and do not contribute to auxiliary space.
c) Storage required for the input is O(n) + O(n) = O(n).

2] Auxiliary Space Complexity (Extra Space Used) : O(n)

Frequency Hash Table (count_map) : O(n)

a) We use a hash map to store the count of each ID appearing in nums.
b) In the worst case, all n elements are unique, leading to n keys in the hash map.
c) Each hash map entry stores an integer value, contributing O(n) space.

Answer List (ans) : O(n)

a) We store the maximum frequency after each step in an array of length n.
b) This requires O(n) space.

Loop Variables and Temporary Storage : O(1)

a) We use variables for iteration, hash map lookups, and temporary values to compute the maximum frequency.
b) These take O(1) space, which is negligible compared to hash map and list storage.

3] Total Space Complexity : O(n)

a) Auxiliary Space Complexity: O(n) (hash map) + O(n) (answer list) = O(n).
b) Total Space Complexity (Including Input): O(n) (input) + O(n) (auxiliary) = O(n).

Thus, the total space complexity is O(n),

The bridge between the brute force and the optimized approach is using a data structure which instead of scanning the entire frequency map at every step to find the maximum (brute force) gives us the maximum views in less computations than the brute force.

Optimal Approach

Intuition

The core intuition behind the Most Frequent IDs example's optimal approach is: rather than scanning through every product (or ID) for every update, you maintain a dynamic record that quickly tells you the top performer. Now the idea is to use a data structure that can do it easily. Instead of repeatedly scanning through the hash map each time we need to dynamically add the key value pair in a data structure that instantly gives us the max frequency. This is when heap comes into play.

What is Heap?

A heap is a specialized tree-based data structure often used to implement priority queues. Heaps are usually implemented as complete binary trees (every level is fully filled except possibly the last, and all nodes are as far left as possible), which allows them to be efficiently stored in an array. With a heap, you can quickly access the minimum or maximum element in constant time, and insertion or deletion operations take logarithmic time. This makes heaps extremely useful in algorithms that require repeated retrieval of the "best" element, like scheduling tasks or sorting data with heapsort.

What is min-heap?
A min-heap is a specialized binary tree-based data structure where the smallest element is always at the root. This means that for any given node in the tree, its value is less than or equal to the values of its children. Because of this property, you can quickly access the minimum element at any time. Additionally, a min-heap is usually implemented as a complete binary tree, which means all levels of the tree are fully filled except possibly the last level, and all nodes in the last level are as far left as possible.

What is max-heap?
A max-heap is a complete binary tree data structure where every parent node has a value greater than or equal to its children, ensuring that the largest element is always at the root. This property makes it easy to quickly access the maximum element. Like a min-heap, a max-heap is typically implemented using an array, which efficiently represents the complete binary tree.

General Operations on Heap:

  • Insertion:
    Inserting an element takes O(log n) time because after placing the new element at the end of the array, you "bubble up" (or "sift up") to restore the heap property.
  • Removal (Extract-Min/Extract-Max):
    Removing the root element (the minimum in a min-heap or maximum in a max-heap) also takes O(log n) time since after removal, you "bubble down" (or "sift down") the last element placed at the root to reestablish the heap property.
  • Peek (Find-Min/Find-Max):
    Retrieving the root element is an O(1) operation because it is always at the front of the array.
  • Building a Heap:
    Building a heap from an unsorted array can be done in O(n) time using a bottom-up heapify process.
  • Space Complexity:
    The heap uses O(n) space to store n elements.

In this optimal method, a max heap (or priority queue) is like an ever-updating scoreboard that holds snapshots of product sales. Each time a product's sales change, you record its new sales count on the scoreboard. However, since sales can change rapidly, older snapshots on the scoreboard may no longer be accurate. To handle this, you check the most recent score against the current record before announcing the leader—this is known as lazy deletion. By doing this, you ensure that, even if the scoreboard has some outdated information, you always verify and present the correct top-selling product without having to re-scan every record.

This approach saves time and effort, much like having a trusted system that continuously and efficiently keeps track of the leader in a dynamic environment, ensuring you always know the current champion without the need for a full recount each time an update occurs.

What is the main purpose of using a max heap (priority queue) in this approach?

The max heap is used to always have quick access to the highest frequency value. Instead of scanning through all entries to find the maximum after each update (as in brute force), the heap keeps the most frequent ID at the top, allowing for faster retrieval.

How does lazy deletion work in the context of our optimal approach?

Lazy deletion means we do not immediately remove outdated frequency records from the heap when an ID's count changes. Instead, when we need the current maximum, we check the top of the heap against the latest value in the hashmap. If they don't match, we remove the stale entry and continue until we find a valid one, ensuring the result is accurate.

Approach

Step 1: Initialize Data Structures

  • Create a hashmap (e.g., unordered_map<int, long long>) to maintain the current frequency of each ID.
  • Initialize a max heap (priority queue) to store pairs of (frequency, ID) so that the highest frequency is always on top.

Step 2: Process Each Operation

  • For each index in the input arrays:
  • Update the frequency of the current ID in the hashmap based on whether you're adding or removing (using the freq value).

Step 3: Update the Heap

  • After updating the hashmap, push a new pair (current frequency of the ID, ID) into the max heap.
  • This records the latest frequency for that ID.

Step 4: Maintain the Valid Top Element (Lazy Deletion)

  • Check the top element of the heap.
  • While the frequency stored at the top of the heap does not match the current frequency in the hashmap (indicating that it's outdated), pop the top element off the heap.
  • Continue this process until the top element is valid.

Step 5: Record the Result

  • The top of the heap now holds the current maximum frequency.
  • Append this maximum frequency to your answer list.

Step 6: Return the Answer

  • After processing all operations, return the list containing the maximum frequency after each update.

Dry Run Most Frequent IDs Algorithm's Dry Run is as follows:

Let's walk through a dry run for the optimal approach using the following example:

  • nums: [2, 3, 2, 1]
  • freq: [3, 2, -3, 1]

Iteration 1 (i = 0):

  • We update the frequency for ID 2: initially, mp[2] becomes 3 (0 + 3).
  • We push (3, 2) into the max heap.
  • Since mp[2] is 3 (nonzero), nothing is removed.
  • When checking the heap, the top is (3, 2), which is valid because mp[2] is still 3.
  • We record the maximum frequency 3.

Iteration 2 (i = 1):

  • Now, we update ID 3: mp[3] becomes 2 (0 + 2).
  • We push (2, 3) into the heap.
  • The heap now has (3, 2) and (2, 3).
  • Checking the top, (3, 2) is still valid (mp[2] remains 3).
  • The maximum frequency remains 3, so we record 3.

Iteration 3 (i = 2):

  • We update ID 2 again with a frequency of -3. This changes mp[2] from 3 to 0.
  • We push (0, 2) into the heap.
  • Since mp[2] is now 0, we erase it from the map.
  • Now, the heap still contains the stale entry (3, 2), along with (2, 3) and (0, 2).
  • In the while loop, we check the top: (3, 2) is on top, but since ID 2 no longer exists in mp (or would be 0 if present), this entry is outdated. We pop it.
  • The next top is (2, 3), and it’s valid because mp[3] is 2.
  • We record the maximum frequency 2.

Iteration 4 (i = 3):

  • We update ID 1: mp[1] becomes 1 (0 + 1).
  • We push (1, 1) into the heap.
  • The heap now contains (2, 3), (0, 2), and (1, 1).
  • The top remains (2, 3) (since 2 is the highest frequency among these).
  • Checking the validity, (2, 3) is valid because mp[3] is 2.
  • We record the maximum frequency 2.

Final Answer: The recorded maximum frequencies after each update are [3, 3, 2, 2].

This dry run shows how the priority queue (max heap) maintains the highest frequency efficiently while lazy deletion removes stale entries, bridging the gap between the brute force scan and a more optimal retrieval strategy.

Code for All Languages
Most Frequent IDs solution in C++ :Optimal 
class Solution
{
public:
    vector<long long> mostFrequentIDs(vector<int> &nums, vector<int> &freq)
    {
        priority_queue<pair<long long, int>> pq;
        unordered_map<int, long long> mp;
        vector<long long> ans;
        for (int i = 0; i < nums.size(); i++)
        {
            mp[nums[i]] += freq[i];
            pq.push({mp[nums[i]], nums[i]});
            while (!pq.empty())
            {
                pair<long long, int> p = pq.top();
                if (mp[p.second] != p.first)
                    pq.pop();
                else
                    break;
            }
            ans.push_back(pq.top().first);
        }
        return ans;
    }
};

Most Frequent IDs solution in Java :Optimal 
import java.util.*;

class Solution {
    // Custom Pair class to hold frequency and id.
    class Pair {
        long freq;
        int id;
        
        public Pair(long freq, int id) {
            this.freq = freq;
            this.id = id;
        }
    }
    
    public List<Long> mostFrequentIDs(int[] nums, int[] freq) {
        // PriorityQueue with custom comparator to simulate a max heap (largest frequency first)
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> Long.compare(b.freq, a.freq));
        // HashMap to track the current frequency of each id
        Map<Integer, Long> mp = new HashMap<>();
        // List to store the answer after each update
        List<Long> ans = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            int id = nums[i];
            // Update frequency in the map
            long updatedFreq = mp.getOrDefault(id, 0L) + freq[i];
            mp.put(id, updatedFreq);
            
            // Push the new (frequency, id) pair into the priority queue
            pq.offer(new Pair(updatedFreq, id));
            
            // Lazy deletion: remove outdated pairs from the top of the heap
            while (!pq.isEmpty()) {
                Pair top = pq.peek();
                // If the current frequency in the map doesn't match the stored frequency, it's outdated.
                if (mp.getOrDefault(top.id, 0L) != top.freq) {
                    pq.poll();
                } else {
                    break;
                }
            }
            
            // The top of the heap now holds the valid maximum frequency.
            // If the heap becomes empty, the max frequency is 0.
            ans.add(pq.isEmpty() ? 0L : pq.peek().freq);
        }
        
        return ans;
    }
}

Most Frequent IDs solution in Python :Optimal 
import heapq

class Solution:
    def mostFrequentIDs(self, nums, freq):
        mp = {}         # Dictionary to store the current frequency for each ID
        heap = []       # Heap (as a min-heap with negative frequencies to simulate max-heap)
        ans = []        # List to store the maximum frequency after each update
        
        for i in range(len(nums)):
            # Update frequency for current ID
            id_ = nums[i]
            mp[id_] = mp.get(id_, 0) + freq[i]
            
            # Push the new (negative frequency, id) pair into the heap
            heapq.heappush(heap, (-mp[id_], id_))
            
            # Lazy deletion: Remove outdated entries from the top of the heap
            while heap:
                current_freq, current_id = heap[0]
                if -current_freq != mp.get(current_id, 0):
                    heapq.heappop(heap)
                else:
                    break
            
            # The top of the heap now has the valid maximum frequency
            ans.append(-heap[0][0])
        
        return ans

# Example usage:
if __name__ == "__main__":
    sol = Solution()
    nums = [2, 3, 2, 1]
    freq = [3, 2, -3, 1]
    print(sol.mostFrequentIDs(nums, freq))  # Output: [3, 3, 2, 2]

Most Frequent IDs solution in Javascript :Optimal 
/**
 * @param {number[]} nums
 * @param {number[]} freq
 * @return {number[]}
 */
var mostFrequentIDs = function(nums, freq) {
    // Custom MaxHeap implementation using an array
    class MaxHeap {
        constructor() {
            this.heap = [];
        }
        size() {
            return this.heap.length;
        }
        peek() {
            return this.heap[0];
        }
        push(item) {
            this.heap.push(item);
            this._siftUp(this.heap.length - 1);
        }
        pop() {
            const top = this.heap[0];
            const last = this.heap.pop();
            if (this.heap.length > 0) {
                this.heap[0] = last;
                this._siftDown(0);
            }
            return top;
        }
        _siftUp(index) {
            let child = index;
            while (child > 0) {
                let parent = Math.floor((child - 1) / 2);
                // Each item is [frequency, id]. We want the highest frequency at the top.
                if (this.heap[parent][0] < this.heap[child][0]) {
                    [this.heap[parent], this.heap[child]] = [this.heap[child], this.heap[parent]];
                    child = parent;
                } else {
                    break;
                }
            }
        }
        _siftDown(index) {
            let parent = index;
            const n = this.heap.length;
            while (true) {
                let left = 2 * parent + 1;
                let right = 2 * parent + 2;
                let largest = parent;
                if (left < n && this.heap[left][0] > this.heap[largest][0]) {
                    largest = left;
                }
                if (right < n && this.heap[right][0] > this.heap[largest][0]) {
                    largest = right;
                }
                if (largest !== parent) {
                    [this.heap[parent], this.heap[largest]] = [this.heap[largest], this.heap[parent]];
                    parent = largest;
                } else {
                    break;
                }
            }
        }
    }
    
    let mp = new Map();  // Map to store current frequency for each ID.
    let heap = new MaxHeap();  // Max heap to quickly retrieve the highest frequency.
    let ans = [];
    
    // Process each update.
    for (let i = 0; i < nums.length; i++) {
        let id = nums[i];
        // Update frequency for the current id.
        let updatedFreq = (mp.get(id) || 0) + freq[i];
        mp.set(id, updatedFreq);
        
        // Push the updated pair [frequency, id] into the heap.
        heap.push([updatedFreq, id]);
        
        // Lazy deletion: Remove stale entries from the top.
        while (heap.size() > 0) {
            let top = heap.peek();
            if (mp.get(top[1]) !== top[0]) {
                heap.pop();
            } else {
                break;
            }
        }
        
        // The top of the heap now has the valid maximum frequency.
        ans.push(heap.size() > 0 ? heap.peek()[0] : 0);
    }
    
    return ans;
};

Most Frequent IDs complexity analysis:Time Complexity O(n log n).

  1. Iteration Over Input (n iterations): O(n)
    We iterate through each element in the nums and freq arrays, which takes O(n) iterations.
  2. Updating the Frequency Map: O(1)
    For each iteration, updating the unordered_map (mp[nums[i]] += freq[i]) takes O(1) on average.
  3. Pushing into the Priority Queue: O(nlog n)
    Each push operation into the priority queue takes O(log k), where k is the number of elements in the heap. In the worst case, the heap size can grow to O(n), making each push O(log n).
  4. Lazy Deletion (While Loop): O(nlog n)
    Within each iteration, we might pop outdated entries from the heap. Each pop is O(log n). Although, in the worst-case scenario, many pops might occur in a single iteration, each pushed element can be popped only once overall. Therefore, when summed over all iterations, the total cost of all pop operations is O(n log n) amortized.
  5. Overall Time Complexity: O(nlog n).
    • Frequency map updates: O(n)
    • Heap push operations: O(n log n)
    • Heap pop operations: O(n log n)
      Combining these, the overall worst-case time complexity is O(n log n).

Thus, by using a max heap with lazy deletion, the algorithm efficiently reduces the scanning cost of the brute force approach to an overall O(n log n) time complexity.

Most Frequent IDs complexity analysis:Space Complexity O(n).

Auxiliary Space Complexity: O(n)

  • Priority Queue (Max Heap): In each iteration, we push one pair into the heap. In the worst-case scenario, if none of the pushed pairs are removed by lazy deletion, the heap can store up to O(n) pairs.
  • Hash Map: The unordered_map keeps track of frequencies for each unique ID. In the worst case (all IDs are distinct), it holds O(n) entries.
  • Answer Vector: We record one result per operation, so the answer vector holds O(n) elements.
    Combined, these extra data structures use O(n) space overall.

Total Space Complexity: O(n)

  • In addition to the auxiliary space, the input arrays (nums and freq) also require O(n) space.
  • Therefore, when considering both the input and the auxiliary data, the total space complexity remains O(n).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Similar Problems

Most Frequent Prime

Given an m×n matrix of digits, generate numbers by moving in any of the 8 directions (without changing direction mid-path). At each step, form numbers by appending digits sequentially. Find the most frequent prime number greater than 10 among all generated numbers. If multiple primes have the highest frequency, return the largest; otherwise, return -1.

Minimum Time to Complete All Tasks

This problem asks you to determine the minimum total time a computer needs to be turned on to complete a set of tasks. Each task has a specific duration it must run (which can be non-continuous) and must be executed within a given time window [start, end]. Since the computer can run an unlimited number of tasks concurrently, the challenge is to schedule the tasks optimally, ensuring the computer is only on when necessary to fulfill all required durations.