Most Frequent IDs - Practice Coding Problems

Most Frequent IDs - Problem

You are given two integer arrays nums and freq of equal length n. Each element nums[i] represents an ID, and the corresponding element freq[i] indicates how many times that ID should be added to or removed from the collection at step i.

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 i-th step. If the collection is empty at any step, ans[i] should be 0 for that step.

Input & Output

Example 1 — Basic Operations

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

› Output: [3,3,2,2]

💡 Note: Step 0: Add 3 of ID 2 → {2:3} → max = 3. Step 1: Add 2 of ID 3 → {2:3,3:2} → max = 3. Step 2: Remove 3 of ID 2 → {3:2} → max = 2. Step 3: Add 1 of ID 1 → {3:2,1:1} → max = 2.

Example 2 — Collection Becomes Empty

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

› Output: [2,0,1]

💡 Note: Step 0: Add 2 of ID 5 → {5:2} → max = 2. Step 1: Remove 2 of ID 5 → {} → max = 0. Step 2: Add 1 of ID 3 → {3:1} → max = 1.

Example 3 — Same ID Multiple Updates

$ Input: nums = [1,1,1], freq = [1,1,1]

› Output: [1,2,3]

💡 Note: Step 0: Add 1 of ID 1 → {1:1} → max = 1. Step 1: Add 1 more of ID 1 → {1:2} → max = 2. Step 2: Add 1 more of ID 1 → {1:3} → max = 3.

Constraints

1 ≤ nums.length == freq.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
-10⁵ ≤ freq[i] ≤ 10⁵
freq[i] ≠ 0
The collection will never have a negative count for any ID

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: IDs and their frequency changes

Process

Update collection and find maximum frequency

Output

Array of maximum frequencies after each step

Key Takeaway

🎯 Key Insight: Use heap to efficiently track maximum frequency as the collection changes over time

Asked in

G Google 35 M Meta 28 a Amazon 22 Apple 18

Track ID frequencies with a hash map and use a max heap to efficiently maintain the maximum frequency. The key insight is that we only need to track frequency values in the heap, not individual IDs. Best approach uses heap with O(n log k) time complexity where k is the number of distinct frequency values.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Max Tracking	O(n²)	O(n)	Use hash map for frequencies and track maximum frequency separately
Brute Force with Hash Map and Linear Search	O(n²)	O(n)	Track frequencies in hash map, scan all values to find maximum after each step
Optimized with Heap (Priority Queue)	O(n log k)	O(n)	Use hash map for frequencies and max heap to efficiently track maximum frequency

Hash Map with Max Tracking — Algorithm Steps

Update frequency count in hash map
Track maximum frequency separately
Update max when frequency increases or remove when it decreases

Visualization

Tap to expand

Step-by-Step Walkthrough

Update Map

Update frequency count in hash map

Max Function

Use built-in max() on all values

Store Result

Record maximum frequency

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct FreqEntry {
    int id;
    int count;
};

int* solution(int* nums, int numsSize, int* freq, int freqSize, int* returnSize) {
    struct FreqEntry entries[1000];
    int entryCount = 0;
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;
    
    for (int i = 0; i < numsSize; i++) {
        // Find or create entry for nums[i]
        int found = -1;
        for (int j = 0; j < entryCount; j++) {
            if (entries[j].id == nums[i]) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            entries[entryCount].id = nums[i];
            entries[entryCount].count = freq[i];
            entryCount++;
        } else {
            entries[found].count += freq[i];
        }
        
        // Remove entries with zero or negative count
        for (int j = 0; j < entryCount; j++) {
            if (entries[j].count <= 0) {
                for (int k = j; k < entryCount - 1; k++) {
                    entries[k] = entries[k + 1];
                }
                entryCount--;
                j--;
            }
        }
        
        // Find maximum frequency using built-in max logic
        int maxFreq = 0;
        for (int j = 0; j < entryCount; j++) {
            if (entries[j].count > maxFreq) {
                maxFreq = entries[j].count;
            }
        }
        
        result[i] = maxFreq;
    }
    
    return result;
}

int main() {
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, still need to scan all frequencies when max element is removed

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores frequency counts for up to n different IDs

⚡ Linearithmic Space

23.4K Views

Medium-High Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Max Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler