Problem Description

You are given two integer arrays nums and freq, both of length n. These arrays work together to describe a series of operations on a collection of IDs.

For each index i from 0 to n-1:

• nums[i] represents an ID value
• freq[i] represents how many times that ID should be added or removed:
  • If freq[i] > 0: Add freq[i] copies of ID nums[i] to the collection
  • If freq[i] < 0: Remove -freq[i] copies of ID nums[i] from the collection

Your task is to track the frequency of the most common ID after each operation. Return an array ans of length n where ans[i] represents the count of the most frequent ID in the collection after completing the operation at index i.

If the collection becomes empty at any point, the answer for that step should be 0.

For example, if you have:

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

The operations would be:

1. Add 3 copies of ID 2 → Collection has {2: 3}, most frequent count is 3
2. Add 2 copies of ID 3 → Collection has {2: 3, 3: 2}, most frequent count is 3
3. Remove 1 copy of ID 2 → Collection has {2: 2, 3: 2}, most frequent count is 2
4. Add 1 copy of ID 1 → Collection has {2: 2, 3: 2, 1: 1}, most frequent count is 2

The answer would be [3, 3, 2, 2].

Intuition

The key challenge is efficiently tracking the maximum frequency after each operation. A naive approach would be to scan through all ID frequencies after each update, but this would be too slow for large inputs.

We need a data structure that can quickly give us the maximum value - a max heap (priority queue) is perfect for this. However, there's a complication: when we update an ID's frequency, its old frequency value might still be sitting in the heap.

For example, if ID 2 has frequency 5 and we add 3 more, its new frequency is 8. But the heap now contains both 5 and 8 for the same ID. We can't efficiently remove the outdated 5 from the middle of the heap.

The clever insight is to use a "lazy deletion" strategy. Instead of removing outdated values immediately, we:

1. Keep track of how many times each frequency value is outdated using a lazy counter
2. When a frequency changes from old_freq to new_freq, we mark old_freq as needing deletion by incrementing lazy[old_freq]
3. Add the new_freq to the heap regardless

When we need the maximum frequency, we peek at the top of the heap. If that value has pending deletions (i.e., lazy[top] > 0), we know it's outdated, so we pop it and decrement its lazy counter. We repeat this until we find a valid maximum or the heap is empty.

This approach works because:

• We only care about the maximum value at each step
• Outdated values that aren't at the top don't affect our answer
• We clean up outdated values lazily, only when they bubble up to the top
• Each value is added once and removed once, maintaining efficiency

The cnt hash table tracks current frequencies of each ID, while the heap combined with lazy deletion gives us quick access to the maximum frequency at any point.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution uses a combination of hash tables and a max heap with lazy deletion to efficiently track the maximum frequency after each operation.

Data Structures Used:

• cnt: A Counter (hash table) that stores the current frequency of each ID
• lazy: A Counter that tracks how many times each frequency value needs to be deleted from the heap
• pq: A min heap (negated values to simulate max heap) that stores all frequency values
• ans: The result array

Step-by-Step Implementation:

1. Initialize data structures:

   cnt = Counter()  # ID -> current frequency
   lazy = Counter() # frequency value -> deletion count
   ans = []         # result array
   pq = []          # priority queue (max heap)

2. Process each operation (x, f):

   a. Mark old frequency for lazy deletion:

   lazy[cnt[x]] += 1

   Before updating, we mark the current frequency of ID x as outdated by incrementing its count in lazy.

   b. Update the frequency:

   cnt[x] += f

   Add f to the frequency of ID x (can be positive or negative).

   c. Add new frequency to heap:

   heappush(pq, -cnt[x])

   Push the new frequency to the heap (negated for max heap behavior).

   d. Clean up outdated values at the top:

   while pq and lazy[-pq[0]] > 0:
       lazy[-pq[0]] -= 1
       heappop(pq)

   While the top of the heap has pending deletions, remove it and decrement its lazy counter.

   e. Record the maximum frequency:

   ans.append(0 if not pq else -pq[0])

   If the heap is empty, the maximum frequency is 0; otherwise, it's the negated top value.

Why This Works:

• The heap always contains all frequency values that have ever existed
• The lazy counter tells us which values are outdated
• We only clean up outdated values when they reach the top of the heap
• This ensures O(log n) time for heap operations while avoiding expensive deletions from the middle of the heap

Time Complexity: O(n log n) where n is the length of the input arrays Space Complexity: O(n) for the hash tables and heap

Example Walkthrough

Let's trace through a small example to understand how the solution works:

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

Initial State:

• cnt = {} (empty)
• lazy = {} (empty)
• pq = [] (empty heap)
• ans = [] (result array)

Operation 1: Add 2 copies of ID 1

• lazy[cnt[1]] → lazy[0] = 1 (mark old frequency 0 for deletion)
• cnt[1] = 0 + 2 = 2 (update frequency)
• Push -2 to heap → pq = [-2]
• Clean top: Check lazy[2] = 0 (no deletion needed)
• Append 2 to answer → ans = [2]

Operation 2: Add 3 copies of ID 2

• lazy[cnt[2]] → lazy[0] = 2 (mark old frequency 0 for deletion)
• cnt[2] = 0 + 3 = 3 (update frequency)
• Push -3 to heap → pq = [-3, -2]
• Clean top: Check lazy[3] = 0 (no deletion needed)
• Append 3 to answer → ans = [2, 3]

Operation 3: Remove 1 copy of ID 1

• lazy[cnt[1]] → lazy[2] = 1 (mark old frequency 2 for deletion)
• cnt[1] = 2 + (-1) = 1 (update frequency)
• Push -1 to heap → pq = [-3, -2, -1]
• Clean top: Check lazy[3] = 0 (no deletion needed)
• Append 3 to answer → ans = [2, 3, 3]

Operation 4: Add 1 copy of ID 2

• lazy[cnt[2]] → lazy[3] = 1 (mark old frequency 3 for deletion)
• cnt[2] = 3 + 1 = 4 (update frequency)
• Push -4 to heap → pq = [-4, -3, -2, -1]
• Clean top: Check lazy[4] = 0 (no deletion needed)
• Append 4 to answer → ans = [2, 3, 3, 4]

Final Result: [2, 3, 3, 4]

Notice how:

• The heap contains all frequency values ever created: [-4, -3, -2, -1]
• The lazy counter tracks outdated values: {0: 2, 2: 1, 3: 1}
• We only clean outdated values when they reach the top (which didn't happen in this example)
• The current state is: ID 1 has frequency 1, ID 2 has frequency 4

If we continued with an operation that reduced ID 2's frequency, the outdated -4 would eventually reach the top and get lazily deleted.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm iterates through the input arrays once, performing n iterations where n is the length of the arrays. In each iteration:

• Counter updates (cnt[x] and lazy operations) take O(1) time
• heappush operation takes O(log k) time where k is the heap size
• The while loop performs heappop operations, each taking O(log k) time

The key insight is that although there's a while loop inside the main loop, each frequency value can be pushed to the heap and popped at most once throughout the entire execution. Since we perform at most n push operations and at most n pop operations total across all iterations, the amortized time complexity is O(n × log n).

Space Complexity: O(n)

The space usage comes from:

• cnt Counter: stores at most n unique IDs, so O(n) space
• lazy Counter: tracks outdated heap values, at most O(n) entries
• pq heap: can contain at most n elements in the worst case
• ans list: stores exactly n results

All data structures use linear space with respect to the input size n, resulting in a total space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Negative Frequencies Resulting in Zero Count

The Pitfall: When freq[i] is negative and reduces an ID's count to zero or below, developers often forget to properly handle this edge case. If an ID's frequency becomes 0, it should be treated as if it doesn't exist in the collection, but the heap might still contain its old positive frequency values.

Problematic Code:

# Incorrect: Not handling zero or negative frequencies properly
id_frequency[id_value] += frequency_change
if id_frequency[id_value] > 0:
    heapq.heappush(max_heap, -id_frequency[id_value])

The Issue: This approach fails to add zero frequencies to the heap, which means the lazy deletion mechanism won't work correctly. The heap needs ALL frequency transitions to properly track what values are outdated.

Correct Solution:

# Always update and push to heap, even for zero or negative values
outdated_frequencies[id_frequency[id_value]] += 1
id_frequency[id_value] += frequency_change
heapq.heappush(max_heap, -id_frequency[id_value])

2. Incorrect Lazy Deletion Timing

The Pitfall: Marking the old frequency as outdated AFTER updating the frequency count, which causes the wrong value to be marked for deletion.

Problematic Code:

# Incorrect order: updating frequency before marking old value as outdated
id_frequency[id_value] += frequency_change
outdated_frequencies[id_frequency[id_value]] += 1  # Wrong! This marks the NEW frequency
heapq.heappush(max_heap, -id_frequency[id_value])

The Issue: This marks the NEW frequency as outdated instead of the OLD one, leading to incorrect maximum frequency calculations.

Correct Solution:

# Mark old frequency BEFORE updating
outdated_frequencies[id_frequency[id_value]] += 1  # Marks OLD frequency
id_frequency[id_value] += frequency_change         # Now update
heapq.heappush(max_heap, -id_frequency[id_value]) # Push NEW frequency

3. Not Handling Empty Collection Properly

The Pitfall: Assuming the heap always has valid values without checking if all IDs have been removed from the collection.

Problematic Code:

# Incorrect: Always returning the heap top without checking if collection is empty
result.append(-max_heap[0])  # Crashes if heap is empty!

Correct Solution:

# Check if heap is empty after cleanup
result.append(0 if not max_heap else -max_heap[0])

4. Using Regular Heap Instead of Handling Negative Values

The Pitfall: Python's heapq is a min heap, so directly using it without negation will give the minimum frequency instead of maximum.

Problematic Code:

# Incorrect: Using min heap directly
heapq.heappush(max_heap, id_frequency[id_value])  # This creates a MIN heap
result.append(max_heap[0] if max_heap else 0)     # Returns MINIMUM frequency

Correct Solution:

# Negate values for max heap behavior
heapq.heappush(max_heap, -id_frequency[id_value])  # Negative for max heap
result.append(-max_heap[0] if max_heap else 0)     # Negate back when retrieving