Skip to content

3092. Most Frequent IDs 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
    vector<long long> ans;
    unordered_map<int, long> numCount;  // {num: freq}
    map<long, int> freqCount;           // {num's freq: freq}

    for (int i = 0; i < nums.size(); ++i) {
      const int num = nums[i];
      const int f = freq[i];
      if (const auto it = numCount.find(num); it != numCount.cend()) {
        const int numFreq = it->second;
        if (--freqCount[numFreq] == 0)
          freqCount.erase(numFreq);
      }
      const long newFreq = numCount[num] + f;
      if (newFreq == 0) {
        numCount.erase(num);
      } else {
        numCount[num] = newFreq;
        ++freqCount[newFreq];
      }
      ans.push_back(freqCount.empty() ? 0 : freqCount.rbegin()->first);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public long[] mostFrequentIDs(int[] nums, int[] freq) {
    long[] ans = new long[nums.length];
    Map<Integer, Long> numCount = new HashMap<>();      // {num: freq}
    TreeMap<Long, Integer> freqCount = new TreeMap<>(); // {num's freq: freq}

    for (int i = 0; i < nums.length; ++i) {
      final int num = nums[i];
      final int f = freq[i];
      if (numCount.containsKey(num)) {
        final long numFreq = numCount.get(num);
        if (freqCount.merge(numFreq, -1, Integer::sum) == 0)
          freqCount.remove(numFreq);
      }
      final long newFreq = numCount.getOrDefault(num, 0L) + f;
      if (newFreq == 0) {
        numCount.remove(num);
      } else {
        numCount.put(num, newFreq);
        freqCount.merge(newFreq, 1, Integer::sum);
      }
      ans[i] = freqCount.isEmpty() ? 0 : freqCount.lastKey();
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from sortedcontainers import SortedDict


class Solution:
  def mostFrequentIDs(self, nums: list[int], freq: list[int]) -> list[int]:
    ans = []
    numCount = collections.Counter()  # {num: freq}
    freqCount = SortedDict()  # {num's freq: freq}

    for num, f in zip(nums, freq):
      if numCount[num] > 0:
        numFreq = numCount[num]
        freqCount[numFreq] -= 1
        if freqCount[numFreq] == 0:
          del freqCount[numFreq]
      newFreq = numCount[num] + f
      if newFreq == 0:
        del numCount[num]
      else:
        numCount[num] = newFreq
        freqCount[newFreq] = freqCount.get(newFreq, 0) + 1
      ans.append(freqCount.peekitem(-1)[0] if freqCount else 0)

    return ans