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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Frequent IDs

Number: 3363

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given two arrays of equal length – one containing IDs (nums) and the other containing corresponding frequency changes (freq) – update a collection by adding or removing the specified number of IDs in each step. After each operation, determine the count of the most frequent ID in the collection. If the collection is empty, the answer for that step is 0.

Key Insights

  • Use a hash map (dictionary) to track the current count for each ID.
  • Maintain an additional data structure to quickly determine the maximum frequency among all IDs.
  • When an ID’s frequency is changed, update both the ID count mapping and a frequency-to-count mapping.
  • If the highest frequency count becomes zero after a removal, recalculate the new maximum frequency.
  • The guarantee that removal will never lead to negative counts simplifies updates.

Space and Time Complexity

Time Complexity: O(n * k) in the worst case if recalculating the max frequency takes O(k) time (where k is the number of distinct frequencies); however, common cases will be much faster. Space Complexity: O(n) for storing counts and frequency mappings.

Solution

We solve this problem by maintaining two hash maps:

  1. idCount: maps each ID to its current count in the collection.
  2. freqCount: maps frequency values to the number of IDs having that frequency.

For each step:

  • Retrieve the old frequency of the current ID.
  • Update idCount and adjust freqCount by decrementing the count for the old frequency (if any) and incrementing the new frequency.
  • Use a global variable maxFreq to track the highest frequency after each operation. When adding counts, update maxFreq if the new count is larger. When removing counts, if the old maximum frequency’s tally drops to zero, recalculate maxFreq from freqCount.
  • Append maxFreq (or 0 if the collection is empty) to the answer list.

This approach ensures that we correctly compute the most frequent ID count after each update.

Code Solutions

# Python solution
def mostFrequentIDs(nums, freq):
    # Dictionary to maintain current count for each ID
    idCount = {}
    # Dictionary to maintain frequency counts: frequency value -> number of IDs with that frequency
    freqCount = {}
    # Helper function to update freqCount for a given frequency value by a change amount
    def updateFreqCount(frequency, delta):
        if frequency <= 0:
            return
        freqCount[frequency] = freqCount.get(frequency, 0) + delta
        if freqCount[frequency] == 0:
            del freqCount[frequency]
    
    ans = []
    maxFreq = 0
    n = len(nums)
    for i in range(n):
        id_val = nums[i]
        change = freq[i]
        oldCount = idCount.get(id_val, 0)
        newCount = oldCount + change
        
        # Update the frequency counters for the old count
        if oldCount > 0:
            updateFreqCount(oldCount, -1)
        
        # Update the new count for the current ID in idCount mapping
        if newCount > 0:
            idCount[id_val] = newCount
            updateFreqCount(newCount, 1)
        else:
            # If newCount is 0, remove the ID from the map
            if id_val in idCount:
                del idCount[id_val]
        
        # Update maxFreq: if adding, update maxFreq if newCount is greater.
        if newCount > maxFreq:
            maxFreq = newCount
        else:
            # If removal affected the current maxFreq and no IDs have that frequency, recalc the max frequency.
            if maxFreq not in freqCount:
                maxFreq = max(freqCount.keys(), default=0)
        
        ans.append(maxFreq)
    return ans

# Example usage:
print(mostFrequentIDs([2,3,2,1], [3,2,-3,1]))  # Expected output: [3,3,2,2]
print(mostFrequentIDs([5,5,3], [2,-2,1]))        # Expected output: [2,0,1]
← Back to All Questions