Most frequent ids

Array Hash Table Heap (Priority Queue) Ordered Set

42.5% acceptance

Feb 25, 2026

268

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. If freq[i] is positive, freq[i] IDs with the value nums[i] are added to the collection at step i. If freq[i] is negative, -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 ith step.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn most_frequent_i_ds(nums: Vec<i32>, freq: Vec<i32>) -> Vec<i64> {
    use std::collections::{HashMap, BTreeMap};
    let n = nums.len();
    let mut cnt: HashMap<i32, i64> = HashMap::new();
    let mut sorted: BTreeMap<i64, i64> = BTreeMap::new(); // freq_count -> count
    let mut ans = vec![0i64; n];
    for i in 0..n {
      let id = nums[i];
      let f = freq[i] as i64;
      let old = *cnt.get(&id).unwrap_or(&0);
      let new = old + f;
      cnt.insert(id, new);
      if old > 0 {
        let e = sorted.entry(old).or_insert(0);
        *e -= 1;
        if *e == 0 { sorted.remove(&old); }
      }
      if new > 0 {
        *sorted.entry(new).or_insert(0) += 1;
      }
      ans[i] = sorted.keys().next_back().copied().unwrap_or(0);
    }
    ans
  }
}