3092. Most Frequent IDs LeetCode Solution

In this guide, you will get 3092. Most Frequent IDs LeetCode Solution with the best time and space complexity. The solution to Most Frequent IDs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Most Frequent IDs solution in C++
Most Frequent IDs solution in Java
Most Frequent IDs solution in Python
Additional Resources

3092. Most Frequent IDs LeetCode Solution image

Problem Statement of Most Frequent IDs

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 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 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 <= 105
1 <= nums[i] <= 105
-105 <= freq[i] <= 105
freq[i] != 0
The input is generated such that the occurrences of an ID will not be negative in any step.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

3092. Most Frequent IDs LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

3092. Most Frequent IDs LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

3092. Most Frequent IDs LeetCode Solution in Python

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
 # code by PROGIEZ