Highest ID Frequency After Each Update
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Highest ID Frequency After Each Update
Start with an empty collection of integer IDs. You are given equally sized arrays `nums` and `freq`, describing updates in order.
At step `i`:
- If `freq[i] > 0`, add `freq[i]` occurrences of ID `nums[i]`.
- If `freq[i] < 0`, remove `-freq[i]` occurrences of that ID.
Return an array `ans` of the same length, where `ans[i]` is the largest occurrence count of any ID immediately after step `i`. If the collection is empty, use zero for that step.
The updates are guaranteed never to make any ID's count negative.
### Examples
**Example 1**
```text
Input: nums = [4,7,4,7,9], freq = [5,5,-3,-5,4]
Output: [5,5,5,2,4]
```
The positive counts after each update are:
```text
{4:5}
{4:5, 7:5}
{4:2, 7:5}
{4:2}
{4:2, 9:4}
```
The third update lowers ID four's count, while ID seven still has count five. The fourth removes ID seven completely.
**Example 2**
```text
Input: nums = [6,6,2,2,6], freq = [3,-3,4,-4,2]
Output: [3,0,4,0,2]
```
The collection becomes empty after steps one and three. ID six can be added again after its earlier occurrences have all been removed.
### Constraints
- `1 <= nums.length == freq.length <= 10^5`.
- `1 <= nums[i] <= 10^5`.
- `-10^5 <= freq[i] <= 10^5`.
- `freq[i] != 0`.
- After every update, every ID's occurrence count is nonnegative.
### Clarifying Questions
- Is the answer an ID or its occurrence count? Return the count, even when several IDs tie.
- Are the deltas cumulative? Yes; update the existing count of the indicated ID.
- Can a count decrease to zero? Yes; that ID then has no occurrences in the collection.
- Can the collection become empty and later become nonempty? Yes.
- May the input request an impossible removal? No; the nonnegative-count guarantee rules it out.
### C++ Interface
```cpp
class Solution {
public:
vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
}
};
```
### Reasoning Checkpoints
- Apply each addition or removal to the correct cumulative ID count.
- Return the greatest count after every step, including ties and empty states.
- Preserve exact output order and justify arithmetic and resource use for all updates.
```hint Keep counts and an ordered view of active IDs
Maintain each ID's current count. Before changing it, remove its old positive-count entry from an ordered structure; then insert the new one if positive. Include the ID in the ordered key so equal counts do not collapse together.
```
Overview: Track additions and removals of integer IDs and return the highest current occurrence count after every update, including empty states.