LeetCode 3092 - Most Frequent IDs

The problem asks us to maintain a collection of IDs that is updated incrementally based on two arrays, nums and freq. Each index i represents a step.

leetcodemediumarrayhash-tableheap-(priority-queue)ordered-set

LeetCode Problem 3092

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem asks us to maintain a collection of IDs that is updated incrementally based on two arrays, nums and freq. Each index i represents a step. At step i, we either add freq[i] copies of nums[i] to the collection if freq[i] is positive, or remove -freq[i] copies of nums[i] if freq[i] is negative. After each step, we need to report the count of the most frequent ID in the current collection. If the collection becomes empty, we return 0 for that step.

The input guarantees that no ID will be removed more than it exists at that point, so we do not need to handle negative frequencies in the collection. The key challenges are:

  1. Keeping track of the frequency of each ID efficiently.
  2. Quickly determining the maximum frequency after each step.

The constraints indicate that nums and freq can each have up to 100,000 elements, and ID values can also reach 100,000. This means any naive approach that scans the entire collection or builds the full list of IDs at each step would be too slow. We must use efficient frequency tracking with max frequency retrieval.

Important edge cases include:

  • IDs being added and fully removed in subsequent steps, leaving the collection empty.
  • Multiple IDs sharing the same maximum frequency.
  • Large positive and negative frequencies at a single step.

Approaches

The brute-force approach would be to maintain a list representing the collection at each step. For each operation, we would add or remove elements explicitly, and then scan the list to count occurrences of each ID to find the maximum frequency. While correct, this approach has poor performance because adding/removing elements in bulk and counting frequencies repeatedly would take O(n^2) in the worst case for large n.

The optimal approach uses a hash map to track the current frequency of each ID and a counter map of counts to frequencies or an ordered data structure to maintain the maximum frequency dynamically. By updating the frequency map incrementally and keeping track of the current maximum, we can compute the maximum frequency after each step in O(1) amortized time per step.

Key insight: Instead of rebuilding the collection or scanning all IDs at each step, we maintain two mappings: id -> count and count -> number of IDs with that count. Updating these maps with each step lets us adjust the current maximum frequency efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Maintain full list of IDs and scan to count frequencies at each step
Optimal O(n) O(n) Use hash maps to track frequencies and counts of frequencies, update max frequency incrementally

Algorithm Walkthrough

  1. Initialize two hash maps: id_count to track the frequency of each ID, and freq_count to track how many IDs have a given frequency. Also, initialize max_freq = 0.

  2. Create an empty list ans to store the maximum frequency after each step.

  3. Iterate over each step i:

  4. Extract num = nums[i] and change = freq[i].

  5. Get the current count old_count of num from id_count, defaulting to 0 if not present.

  6. Update id_count[num] = old_count + change.

  7. Decrement freq_count[old_count] because num no longer has old_count occurrences.

  8. Increment freq_count[new_count] where new_count = old_count + change.

  9. If new_count > max_freq, update max_freq = new_count.

  10. If freq_count[max_freq] == 0 after removing IDs, decrement max_freq until a positive count is found.

  11. Append max_freq to ans.

  12. Return ans.

Why it works: By maintaining the frequency of each ID and the count of how many IDs have each frequency, we can always determine the current maximum frequency efficiently. The maps ensure that updates and maximum checks are quick, without scanning the entire collection.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        id_count = defaultdict(int)  # id -> frequency
        freq_count = defaultdict(int)  # frequency -> number of IDs with that frequency
        max_freq = 0
        ans = []

        for num, change in zip(nums, freq):
            old_count = id_count[num]
            new_count = old_count + change
            id_count[num] = new_count

            if old_count > 0:
                freq_count[old_count] -= 1

            freq_count[new_count] += 1

            if new_count > max_freq:
                max_freq = new_count
            else:
                while max_freq > 0 and freq_count[max_freq] == 0:
                    max_freq -= 1

            ans.append(max_freq)

        return ans

Explanation: The id_count map tracks how many times each ID appears, and freq_count tracks how many IDs have a particular frequency. When an ID's frequency changes, we update both maps. The max_freq is updated dynamically: increased if a new higher frequency appears, or decreased if the previous maximum frequency no longer exists.

Go Solution

package main

func mostFrequentIDs(nums []int, freq []int) []int64 {
	idCount := make(map[int]int)
	freqCount := make(map[int]int)
	ans := make([]int64, len(nums))
	var maxFreq int

	for i, num := range nums {
		change := freq[i]
		oldCount := idCount[num]
		newCount := oldCount + change
		idCount[num] = newCount

		if oldCount > 0 {
			freqCount[oldCount]--
		}
		freqCount[newCount]++

		if newCount > maxFreq {
			maxFreq = newCount
		} else {
			for maxFreq > 0 && freqCount[maxFreq] == 0 {
				maxFreq--
			}
		}

		ans[i] = int64(maxFreq)
	}

	return ans
}

Go-specific notes: We use maps for idCount and freqCount similar to Python. We also use int64 for the output array to satisfy the function signature. Go handles zero-value map lookups safely, so no special defaulting is required.

Worked Examples

Example 1: nums = [2,3,2,1], freq = [3,2,-3,1]

Step Operation id_count freq_count max_freq ans
0 add 3 of 2 {2:3} {3:1} 3 3
1 add 2 of 3 {2:3,3:2} {3:1,2:1} 3 3
2 remove 3 of 2 {2:0,3:2} {3:0,2:1,0:1} 2 2
3 add 1 of 1 {2:0,3:2,1:1} {2:1,1:1,0:1} 2 2

Example 2: nums = [5,5,3], freq = [2,-2,1]

Step Operation id_count freq_count max_freq ans
0 add 2 of 5 {5:2} {2:1} 2 2
1 remove 2 of 5 {5:0} {2:0,0:1} 0 0
2 add 1 of 3 {5:0,3:1} {1:1,0:1} 1 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each step involves constant-time map updates and at most O(max_freq) for decrementing max_freq, but overall amortized O(n)
Space O(n) Maps store counts for each unique ID and frequencies, at most n entries

The approach is efficient because it avoids scanning the entire collection at each step and maintains the maximum frequency dynamically.

Test Cases

sol = Solution()

# Provided examples
assert sol.mostFrequentIDs([2,3,2,1], [3,2,-3,1]) == [3,3,2,2]  # example 1
assert sol.mostFrequentIDs([5,5,3], [2,-2,1]) == [2,0,1]         # example 2

# Boundary cases
assert sol.mostFrequentIDs([1], [1]) == [1]                       # single ID added
assert sol.mostFrequentIDs([1], [-1])