We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Most Frequent IDs

Difficulty: Medium

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

Key Insights

  • Maintain a frequency count of each ID in the collection.
  • Use a max heap (or priority queue) to efficiently track the most frequent ID.
  • Update the frequency count based on the values in the freq array.
  • Handle cases where IDs are removed, ensuring the heap reflects current frequencies accurately.
  • Return the maximum frequency after each step.

Space and Time Complexity

Time Complexity: O(n log k), where n is the number of steps and k is the number of unique IDs. Space Complexity: O(k), where k is the number of unique IDs stored in the frequency map and heap.

Solution

To tackle this problem, we will employ a hash map (or dictionary) to maintain the count of each ID. Additionally, we will utilize a max heap to efficiently retrieve the most frequent ID after each operation. Here's the step-by-step approach:

  1. Initialize a hash map to keep track of the frequencies of each ID.
  2. Use a max heap to store the frequency of IDs along with the ID itself.
  3. For each element in the freq array:
    • Update the frequency of the corresponding ID in the hash map.
    • If the frequency is incremented, add the new frequency to the heap.
    • When the frequency is decremented, check if the ID still exists in the heap.
    • Ensure that the heap's top reflects the correct maximum frequency.
  4. After processing each step, append the current maximum frequency to the result array.
  5. Handle cases where the collection is empty by returning 0 for that step.

Code Solutions

from collections import defaultdict
import heapq

def most_frequent_ids(nums, freq):
    freq_map = defaultdict(int)  # Maps IDs to their frequencies
    max_heap = []  # Max heap to track the most frequent IDs
    ans = []  # Result array
    
    for i in range(len(nums)):
        # Update frequency
        freq_map[nums[i]] += freq[i]
        
        # If adding IDs, push to heap
        if freq[i] > 0:
            heapq.heappush(max_heap, (-freq_map[nums[i]], nums[i]))
        
        # Clean the heap to ensure the top is valid
        while max_heap and -max_heap[0][0] != freq_map[max_heap[0][1]]:
            heapq.heappop(max_heap)
        
        # Record the most frequent ID count
        if max_heap:
            ans.append(-max_heap[0][0])
        else:
            ans.append(0)
    
    return ans
← Back to All Questions