Most Frequent IDs solution and explanation
9 more videos on this problem
Most Frequent IDs | Complete Intuition | Leetcode 3092 | codestorywithMIKcodestorywithMIK · 31:59 · 3K views
3092. Most Frequent IDs | Set | Priority Queue | Hash Maps | Weekly Contest 390Aryan Mittal · 10:09 · 2K views
3092 Most Frequent IDs || why Priority_queue 🤷♂️ || Count MapAyush Rao · 10:57 · 687 views
3092. Most Frequent IDs (Leetcode Medium)Programming Live with Larry · 10:15 · 490 views
Most Frequent IDs - LEETCODE WEEKLY CONTEST 390Joyjit Codes · 4:43 · 197 views
Leetcode 3092: Most Frequent IDsAlgorithms Casts · 13:33 · 164 views
Most Frequent IDs - Leetcode 3092 - DSA - Hashmap - SetTHE CODE CLUB · 10:28 · 68 views
3092. Most Frequent IDs || Leetcode Weekly Contest 390 || HindiAshish Kumar · 15:34 · 53 views
Leetcode 3092: Most Frequent IDs ~ Python Solutionarch_r45 · 20:24 · 43 views
3092. Most Frequent IDs (Explanation) || SEGMENT TREE Approach || Leetcode Weekly contest 390X AlphA - Hard Algorithms · 15:43 · 33 views
The problem
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.
- Addition of IDs: If
freq[i]is positive, it meansfreq[i]IDs with the valuenums[i]are added to the collection at stepi. - Removal of IDs: If
freq[i]is negative, it means-freq[i]IDs with the valuenums[i]are removed from the collection at stepi.
Return an array ans of length n, where ans[i] represents the count of the most frequent ID in the collection after the ith step. If the collection is empty at any step, ans[i] should be 0 for that step.
Example 1:
Input: nums = [2,3,2,1], freq = [3,2,-3,1]
Output: [3,3,2,2]
Explanation:
After step 0, we have 3 IDs with the value of 2. So ans[0] = 3.
After step 1, we have 3 IDs with the value of 2 and 2 IDs with the value of 3. So ans[1] = 3.
After step 2, we have 2 IDs with the value of 3. So ans[2] = 2.
After step 3, we have 2 IDs with the value of 3 and 1 ID with the value of 1. So ans[3] = 2.
Example 2:
Input: nums = [5,5,3], freq = [2,-2,1]
Output: [2,0,1]
Explanation:
After step 0, we have 2 IDs with the value of 5. So ans[0] = 2.
After step 1, there are no IDs. So ans[1] = 0.
After step 2, we have 1 ID with the value of 3. So ans[2] = 1.
Constraints:
1 <= nums.length == freq.length <= 1051 <= nums[i] <= 105-105 <= freq[i] <= 105freq[i] != 0- The input is generated such that the occurrences of an ID will not be negative in any step.
Approach overview
Problem Overview: You receive two arrays: nums (IDs) and freq (frequency changes). After each step, the frequency of nums[i] increases or decreases by freq[i]. After applying the update, return the current maximum frequency among all IDs.
The challenge is maintaining the highest frequency dynamically while updates continuously modify counts. A naive scan after every update would be too slow, so efficient data structures are required to track frequencies in near real time.
Approach 1: Divide and Conquer Approach (Segment Tree over Frequencies) (Time: O(n log n), Space: O(n))
This approach treats the problem as a dynamic range query. First maintain a running frequency map for each ID using a hash table. Each update modifies a single ID’s count. A segment tree or balanced structure tracks the maximum frequency among all IDs. Every update propagates through the tree in O(log n), while the maximum value can be queried in constant time from the root. This divide‑and‑conquer structure splits the range of IDs into segments and combines results from child nodes to compute the global maximum.
This approach works well when the ID space is large but updates are frequent. It keeps operations predictable and avoids repeated scanning of all IDs.
Approach 2: Iterative Approach Using Hash Map + Max Heap (Time: O(n log n), Space: O(n))
The more common solution maintains frequencies using a hash table and tracks the maximum using a max heap (priority queue). For every update, adjust the stored frequency of the ID in the map. Then push the new pair (frequency, id) into the heap. Because heap entries may become outdated after future updates, lazy deletion is used: repeatedly pop the heap top until the frequency matches the current value in the map.
This strategy ensures that the heap always reveals the correct maximum frequency. Each push and cleanup operation costs O(log n), and every element is inserted a limited number of times, keeping total complexity manageable.
An alternative implementation replaces the heap with an ordered set or balanced tree keyed by frequency. That allows direct updates and quick retrieval of the largest frequency.
Recommended for interviews: The hash map + max heap approach is what most interviewers expect. It shows you can combine a frequency map with a priority queue and handle stale entries using lazy deletion. Discussing a simpler brute force scan demonstrates understanding, but implementing the heap-based solution proves you can optimize dynamic queries efficiently.
Approach 1: Divide and Conquer Approach
The divide and conquer strategy involves breaking down the problem into smaller, more manageable sub-problems until they become simple enough to solve directly. This approach is particularly effective when the problem can be split into similar sub-problems which can be solved independently.
def solve(array, low, high):
if low < high:
mid = (low + high) // 2
solve(array, low, mid)
solve(array, mid + 1, high)
# handle merging or combining results
array = [2, 3, 8, 6, 1]
solve(array, 0, len(array) - 1)public class Solution {
public void solve(int[] array, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
solve(array, low, mid);
solve(array, mid + 1, high);
// handle merging or combining results
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] array = {2, 3, 8, 6, 1};
solution.solve(array, 0, array.length - 1);
}
}#include <iostream>
#include <vector>
void solve(std::vector<int>& array, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
solve(array, low, mid);
solve(array, mid + 1, high);
// handle merging or combining results
}
}
int main() {
std::vector<int> array = {2, 3, 8, 6, 1};
solve(array, 0, array.size() - 1);
return 0;
}function solve(array, low, high) {
if (low < high) {
const mid = Math.floor((low + high) / 2);
solve(array, low, mid);
solve(array, mid + 1, high);
// handle merging or combining results
}
}
const array = [2, 3, 8, 6, 1];
solve(array, 0, array.length - 1);#include <stdio.h>
void solve(int* array, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
solve(array, low, mid);
solve(array, mid + 1, high);
// handle merging or combining results
}
}
int main() {
int array[] = {2, 3, 8, 6, 1};
int size = sizeof(array) / sizeof(array[0]);
solve(array, 0, size - 1);
return 0;
}using System;
public class Solution {
public void Solve(int[] array, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
Solve(array, low, mid);
Solve(array, mid + 1, high);
// handle merging or combining results
}
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] array = {2, 3, 8, 6, 1};
solution.Solve(array, 0, array.Length - 1);
}
}This Python solution makes use of recursion in a similar manner to other programming languages. It divides the array into smaller sub-arrays until they are simple enough to handle. The merge operation is a placeholder for further logic specific to the problem.
Time Complexity: O(n log n)
Space Complexity: O(log n)
Approach 2: Iterative Approach Using Auxiliary Data Structures
This approach employs auxiliary data structures such as stacks or queues to avoid recursion, making it an iterative solution. It simulates recursive behavior and is particularly useful when avoiding stack overflow scenarios or reducing function call overheads.
def solve(array):
stack = [(0, len(array) - 1)]
while stack:
low, high = stack.pop()
# handle current sub-array range logic
array = [2, 3, 8, 6, 1]
solve(array)import java.util.Stack;
public class Solution {
public void solve(int[] array) {
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{0, array.length - 1});
while (!stack.isEmpty()) {
int[] range = stack.pop();
int low = range[0];
int high = range[1];
// Process the current range in array
// adapt with specific logic as needed
}
}
public static void main(String[] args) {
int[] array = {2, 3, 8, 6, 1};
new Solution().solve(array);
}
}#include <iostream>
#include <stack>
#include <vector>
void solve(std::vector<int>& array) {
std::stack<std::pair<int, int>> s;
s.push({0, array.size() - 1});
while (!s.empty()) {
int low = s.top().first;
int high = s.top().second;
s.pop();
// process current sub-array range
// replace this comment with logic application
}
}
int main() {
std::vector<int> array = {2, 3, 8, 6, 1};
solve(array);
return 0;
}function solve(array) {
const stack = [[0, array.length - 1]];
while (stack.length) {
const [low, high] = stack.pop();
// logic to solve for current array range
}
}
const array = [2, 3, 8, 6, 1];
solve(array);#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void solve(int* array, int size) {
int* stack = (int*)malloc(size * sizeof(int));
int top = -1;
stack[++top] = 0;
stack[++top] = size - 1;
while (top >= 0) {
int high = stack[top--];
int low = stack[top--];
// process current sub-array range
// instead of mid calculation, task-specific processing
}
free(stack);
}
int main() {
int array[] = {2, 3, 8, 6, 1};
int size = sizeof(array) / sizeof(array[0]);
solve(array, size);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public void Solve(int[] array) {
Stack<(int, int)> stack = new Stack<(int, int)>();
stack.Push((0, array.Length - 1));
while (stack.Count > 0) {
var (low, high) = stack.Pop();
// processing logic for the current array range
}
}
public static void Main(string[] args) {
int[] array = {2, 3, 8, 6, 1};
new Solution().Solve(array);
}
}This Python code uses a list as a stack to replicate recursive processing iteratively. The stack data structure aids in managing array segment processing, advantageous in scenarios involving significantly sized data sets.
Time Complexity: O(n log n)
Space Complexity: O(n)
Approach 3: Hash Table + Priority Queue (Max Heap)
We use a hash table cnt to record the occurrence times of each ID, a hash table lazy to record the number of times each occurrence needs to be deleted, and a priority queue pq to maintain the maximum occurrence times.
For each operation (x, f), we need to update the occurrence times cnt[x] of x, which means the value of cnt[x] in lazy needs to increase by 1, indicating that the number of times this occurrence needs to be deleted increases by 1. Then we update the value of cnt[x], adding f to cnt[x]. Then we add the updated value of cnt[x] to the priority queue pq. Then we check the top element of the priority queue pq. If the number of times the corresponding occurrence needs to be deleted in lazy is greater than 0, we pop the top element. Finally, we judge whether the priority queue is empty. If it is not empty, the top element is the maximum occurrence times, and we add it to the answer array.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
func mostFrequentIDs(nums []int, freq []int) []int64 {
n := len(nums)
cnt := map[int]int{}
lazy := map[int]int{}
ans := make([]int64, n)
pq := hp{}
heap.Init(&pq)
for i, x := range nums {
f := freq[i]
lazy[cnt[x]]++
cnt[x] += f
heap.Push(&pq, cnt[x])
for pq.Len() > 0 && lazy[pq.IntSlice[0]] > 0 {
lazy[pq.IntSlice[0]]--
heap.Pop(&pq)
}
if pq.Len() > 0 {
ans[i] = int64(pq.IntSlice[0])
}
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}Complexity comparison
| Approach | Complexity |
|---|---|
| Divide and Conquer Approach | Time Complexity: O(n log n) |
| Iterative Approach Using Auxiliary Data Structures | Time Complexity: O(n log n) |
| Hash Table + Priority Queue (Max Heap) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Scan | O(n^2) | O(n) | Only for understanding the problem or very small inputs |
| Divide and Conquer (Segment Tree) | O(n log n) | O(n) | When frequent updates require structured range aggregation |
| Hash Map + Max Heap (Lazy Deletion) | O(n log n) | O(n) | General case; simple and widely used interview solution |
| Hash Map + Ordered Set | O(n log n) | O(n) | When a language provides efficient balanced tree or multiset operations |
Frequently asked questions
Is Most Frequent IDs easy or hard?
Most Frequent IDs is considered a medium-level problem. The main difficulty is managing dynamic updates while always returning the correct maximum frequency. Understanding how to combine hash maps with heaps or ordered structures is the key concept.
Most Frequent IDs Python/Java solution
In Python, the problem is typically solved using a dictionary for frequency storage and the heapq module for a priority queue with lazy deletion. In Java, developers use HashMap for frequencies and PriorityQueue for the max heap. Both implementations achieve O(n log n) time complexity.
How to solve Most Frequent IDs in O(n)?
Achieving strict O(n) time is difficult because every update potentially changes the ordering of frequencies. Data structures like heaps or balanced trees are needed to track the maximum efficiently, leading to O(n log n) complexity. The hash map plus max heap approach is considered optimal for this problem.
What is the best approach for Most Frequent IDs?
The most practical solution uses a hash map to store the current frequency of each ID and a max heap (priority queue) to track the largest frequency. Each update pushes a new frequency into the heap and stale entries are removed lazily. This keeps updates efficient with O(log n) heap operations and O(n log n) total complexity.
Is Most Frequent IDs asked at Google/Amazon/Meta?
Problems involving dynamic frequency tracking and priority queues appear frequently in interviews at companies like Amazon, Google, and Meta. Variants that combine hash maps with heaps to maintain top elements are especially common in system and algorithm interviews.
What data structure is used in Most Frequent IDs?
The core data structures are a hash table for tracking the current frequency of each ID and a max heap (priority queue) for retrieving the highest frequency quickly. Some implementations also use ordered sets or balanced binary search trees to maintain sorted frequencies.
What is the time complexity of Most Frequent IDs?
The optimal solution runs in O(n log n) time. Each update modifies a hash map entry in O(1) and inserts a new value into a max heap in O(log n). Lazy removal of outdated heap entries keeps the total heap operations bounded by the number of updates.