# Count Mentions Per User
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-mentions-per-user)
Canonical: https://scaleengineer.com/dsa/problems/count-mentions-per-user
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an integer `numberOfUsers` representing the total number of users and an array `events` of size `n x 3`.

Each `events[i]` can be either of the following two types:

1. **Message Event:** `["MESSAGE", "timestampi", "mentions_stringi"]`  
  * This event indicates that a set of users was mentioned in a message at `timestampi`.
  * The `mentions_stringi` string can contain one of the following tokens:  
    * `id<number>`: where `<number>` is an integer in range `[0,numberOfUsers - 1]`. There can be **multiple** ids separated by a single whitespace and may contain duplicates. This can mention even the offline users.
    * `ALL`: mentions **all** users.
    * `HERE`: mentions all **online** users.
2. **Offline Event:** `["OFFLINE", "timestampi", "idi"]`  
  * This event indicates that the user `idi` had become offline at `timestampi` for **60 time units**. The user will automatically be online again at time `timestampi + 60`.

Return an array `mentions` where `mentions[i]` represents the number of mentions the user with id `i` has across all `MESSAGE` events.

All users are initially online, and if a user goes offline or comes back online, their status change is processed _before_ handling any message event that occurs at the same timestamp.

**Note** that a user can be mentioned **multiple** times in a **single** message event, and each mention should be counted **separately**.

**Example 1:**

**Input:** numberOfUsers = 2, events = \[\["MESSAGE","10","id1 id0"\],\["OFFLINE","11","0"\],\["MESSAGE","71","HERE"\]\]

**Output:** \[2,2\]

**Explanation:**

Initially, all users are online.

At timestamp 10, `id1` and `id0` are mentioned. `mentions = [1,1]`

At timestamp 11, `id0` goes **offline.**

At timestamp 71, `id0` comes back **online** and `"HERE"` is mentioned. `mentions = [2,2]`

**Example 2:**

**Input:** numberOfUsers = 2, events = \[\["MESSAGE","10","id1 id0"\],\["OFFLINE","11","0"\],\["MESSAGE","12","ALL"\]\]

**Output:** \[2,2\]

**Explanation:**

Initially, all users are online.

At timestamp 10, `id1` and `id0` are mentioned. `mentions = [1,1]`

At timestamp 11, `id0` goes **offline.**

At timestamp 12, `"ALL"` is mentioned. This includes offline users, so both `id0` and `id1` are mentioned. `mentions = [2,2]`

**Example 3:**

**Input:** numberOfUsers = 2, events = \[\["OFFLINE","10","0"\],\["MESSAGE","12","HERE"\]\]

**Output:** \[0,1\]

**Explanation:**

Initially, all users are online.

At timestamp 10, `id0` goes **offline.**

At timestamp 12, `"HERE"` is mentioned. Because `id0` is still offline, they will not be mentioned. `mentions = [0,1]`

**Constraints:**

* `1 <= numberOfUsers <= 100`
* `1 <= events.length <= 100`
* `events[i].length == 3`
* `events[i][0]` will be one of `MESSAGE` or `OFFLINE`.
* `1 <= int(events[i][1]) <= 105`
* The number of `id<number>` mentions in any `"MESSAGE"` event is between `1` and `100`.
* `0 <= <number> <= numberOfUsers - 1`
* It is **guaranteed** that the user id referenced in the `OFFLINE` event is **online** at the time the event occurs.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It processes events in chronological order. To do this, it first sorts all events by their timestamps. For events at the same time, offline/online status changes are handled before messages. It maintains the state of each user (specifically, when their offline period ends) and updates the mention counts as it iterates through the sorted events.
**Time:** O(M log M + M * max(N, K))
Where `M` is the number of events, `N` is `numberOfUsers`, and `K` is the max number of `id` mentions in a message.
- Sorting takes `O(M log M)`.
- The main loop runs `M` times. Inside the loop, `"ALL"` and `"HERE"` messages take `O(N)` time, while `"id..."` messages take `O(K)` time. The overall complexity is dominated by the loop, resulting in `O(M log M + M * max(N, K))`. · **Space:** O(N + M)
- `O(N)` for the `mentions` and `offlineUntil` arrays.
- `O(M)` or `O(log M)` for sorting, depending on the implementation.
**Pros:** Simple to understand and implement.; Directly models the sequence of events as described in the problem.
**Cons:** Can be inefficient if `numberOfUsers` (`N`) is very large, as `"ALL"` and `"HERE"` messages require iterating through all users for each such event.
### Explanation
The core idea is to handle events in the exact order they occur. We first sort the entire list of events based on their timestamps. A custom comparator ensures that if two events happen at the same time, `OFFLINE` events are processed before `MESSAGE` events, as required by the problem. We then iterate through this sorted list, maintaining an array, `offlineUntil`, to track each user's status. For each `OFFLINE` event, we update this array. For each `MESSAGE` event, we determine which users are mentioned based on the message type and their current online status, and update their counts in a `mentions` array.

```java
import java.util.*;

class Solution {
    public int[] countMentionsPerUser(int numberOfUsers, String[][] events) {
        // Sort events: by timestamp, then by type (OFFLINE before MESSAGE)
        Arrays.sort(events, (a, b) -> {
            int timeA = Integer.parseInt(a[1]);
            int timeB = Integer.parseInt(b[1]);
            if (timeA != timeB) {
                return Integer.compare(timeA, timeB);
            }
            // OFFLINE ("O") comes before MESSAGE ("M")
            return a[0].compareTo(b[0]);
        });

        int[] mentions = new int[numberOfUsers];
        int[] offlineUntil = new int[numberOfUsers]; // stores timestamp when user is back online

        for (String[] event : events) {
            String type = event[0];
            int timestamp = Integer.parseInt(event[1]);

            if (type.equals("OFFLINE")) {
                int userId = Integer.parseInt(event[2]);
                offlineUntil[userId] = timestamp + 60;
            } else { // MESSAGE
                String payload = event[2];
                if (payload.equals("ALL")) {
                    for (int i = 0; i < numberOfUsers; i++) {
                        mentions[i]++;
                    }
                } else if (payload.equals("HERE")) {
                    for (int i = 0; i < numberOfUsers; i++) {
                        // User is online if their offline period has ended
                        if (offlineUntil[i] <= timestamp) {
                            mentions[i]++;
                        }
                    }
                } else { // "id<number>..."
                    String[] mentionedIds = payload.split(" ");
                    for (String idStr : mentionedIds) {
                        int userId = Integer.parseInt(idStr.substring(2));
                        mentions[userId]++;
                    }
                }
            }
        }
        return mentions;
    }
}
```
### Algorithm
- **Sort Events:** Create a custom data structure for events or use a custom comparator to sort the input `events` array. The primary sorting key is the timestamp (integer value of `events[i][1]`). For ties in timestamp, `OFFLINE` events should come before `MESSAGE` events.
- **Initialize State:**
  - `mentions`: An integer array of size `numberOfUsers`, initialized to all zeros. This will store the final counts.
  - `offlineUntil`: An integer array of size `numberOfUsers`, initialized to all zeros. `offlineUntil[i]` will store the timestamp at which user `i` becomes online again. A user `i` is considered online at time `t` if `offlineUntil[i] <= t`.
- **Iterate and Process:** Loop through the sorted events. For each event at `currentTimestamp`:
  - **If it's an `OFFLINE` event for `userId`:**
    - Update the user's state: `offlineUntil[userId] = currentTimestamp + 60`.
  - **If it's a `MESSAGE` event:**
    - Check the `mentions_string`:
      - **`"ALL"`:** Iterate from `user = 0` to `numberOfUsers - 1` and increment `mentions[user]`.
      - **`"HERE"`:** Iterate from `user = 0` to `numberOfUsers - 1`. For each user, check if they are online at `currentTimestamp` (i.e., `offlineUntil[user] <= currentTimestamp`). If they are, increment `mentions[user]`.
      - **`"id<number> ..."`:** Split the string by spaces. For each token `id<number>`, parse the `<number>` to get the `userId` and increment `mentions[userId]`. No online check is needed for these direct mentions.
- **Return Result:** After processing all events, the `mentions` array holds the final counts.

## Optimized Approach with Pre-calculation and Binary Search
This approach avoids the repeated iteration over all users for `"HERE"` messages. It processes different types of mentions separately to optimize the calculation. `"id"` and `"ALL"` mentions are counted in a straightforward pass. For `"HERE"` mentions, it calculates the total number of times a user *would have been* mentioned if they were always online, and then subtracts the mentions that occurred during their offline periods. This subtraction is done efficiently by pre-collecting all `"HERE"` message timestamps and all user offline intervals, then using binary search to find overlaps.
**Time:** O(M*K + M_h*log(M_h) + M_o*log(M_h))
Where `M` is total events, `K` is max `id` mentions, `M_h` is number of `"HERE"` events, and `M_o` is number of `"OFFLINE"` events.
- The first pass takes `O(M*K)`.
- Sorting `hereTimestamps` takes `O(M_h log M_h)`.
- Calculating offline mentions takes `O(M_o * log M_h)`.
- This simplifies to `O(M*K + M*log M)`, which is more efficient than the simulation approach as it avoids the `O(M*N)` term. · **Space:** O(N + M)
- `O(N)` for the `mentions` array.
- `O(M)` in the worst case to store `hereTimestamps` and `offlineIntervals`.
**Pros:** Asymptotically more efficient, especially for a large `numberOfUsers`.; Decouples the logic for different mention types, which can lead to cleaner, more optimized processing for each type.
**Cons:** More complex to implement due to the multiple stages and the need for binary search.; The logic is less direct than a simple simulation.
### Explanation
Instead of a chronological simulation, this method categorizes and processes events by type for efficiency. In a single pass, it handles direct `"id"` mentions, counts total `"ALL"` mentions, and collects timestamps of `"HERE"` messages and offline intervals for each user. After this pass, the `"ALL"` mentions are added to every user. The main optimization is for `"HERE"` mentions. We sort the list of `"HERE"` timestamps. Then, for each user, we iterate through their offline intervals. For each interval, we use binary search on the sorted timestamps to efficiently count how many `"HERE"` messages occurred while the user was offline. This count is subtracted from the total number of `"HERE"` messages to find the number of mentions they received while online. This avoids the costly `O(N)` scan for every `"HERE"` message.

```java
import java.util.*;

class Solution {
    public int[] countMentionsPerUser(int numberOfUsers, String[][] events) {
        int[] mentions = new int[numberOfUsers];
        int allMentionCount = 0;
        List<Integer> hereTimestamps = new ArrayList<>();
        List<int[]>[] offlineIntervals = new ArrayList[numberOfUsers];
        for (int i = 0; i < numberOfUsers; i++) {
            offlineIntervals[i] = new ArrayList<>();
        }

        // 1. Segregate and Pre-process
        for (String[] event : events) {
            String type = event[0];
            int timestamp = Integer.parseInt(event[1]);
            String payload = event[2];

            if (type.equals("OFFLINE")) {
                int userId = Integer.parseInt(payload);
                offlineIntervals[userId].add(new int[]{timestamp, timestamp + 60});
            } else { // MESSAGE
                if (payload.equals("ALL")) {
                    allMentionCount++;
                } else if (payload.equals("HERE")) {
                    hereTimestamps.add(timestamp);
                } else { // "id<number>..."
                    String[] mentionedIds = payload.split(" ");
                    for (String idStr : mentionedIds) {
                        int userId = Integer.parseInt(idStr.substring(2));
                        mentions[userId]++;
                    }
                }
            }
        }

        // 2. Apply "ALL" mentions
        for (int i = 0; i < numberOfUsers; i++) {
            mentions[i] += allMentionCount;
        }

        // 3. Calculate "HERE" mentions
        Collections.sort(hereTimestamps);
        int totalHereMentions = hereTimestamps.size();

        for (int i = 0; i < numberOfUsers; i++) {
            int mentionsWhileOffline = 0;
            for (int[] interval : offlineIntervals[i]) {
                int start = interval[0];
                int end = interval[1];
                // Count "HERE" messages within the offline interval [start, end)
                int startIndex = findLowerBound(hereTimestamps, start);
                int endIndex = findLowerBound(hereTimestamps, end);
                mentionsWhileOffline += (endIndex - startIndex);
            }
            mentions[i] += (totalHereMentions - mentionsWhileOffline);
        }

        return mentions;
    }

    // Finds the index of the first element >= target
    private int findLowerBound(List<Integer> list, int target) {
        int low = 0, high = list.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
```
### Algorithm
- **Segregate and Pre-process:**
  - Initialize `mentions = int[numberOfUsers]`, `all_mention_count = 0`.
  - Create a list for `"HERE"` message timestamps: `here_timestamps`.
  - Create a data structure to store offline intervals for each user, e.g., an array of lists: `offline_intervals[user] -> list of [start, end)`.
  - Iterate through the `events` array once.
    - For `"id..."` messages, parse the user IDs and directly increment their counts in the `mentions` array.
    - For `"ALL"` messages, increment `all_mention_count`.
    - For `"HERE"` messages, add the timestamp to `here_timestamps`.
    - For `"OFFLINE"` events for user `i` at time `t`, add the interval `[t, t + 60)` to `offline_intervals[i]`.
- **Apply "ALL" Mentions:** Add `all_mention_count` to every user's mention count.
- **Calculate "HERE" Mentions:**
  - Sort the `here_timestamps` list.
  - The total number of `"HERE"` messages is `total_here_mentions = here_timestamps.size()`.
  - For each user `i`:
    - Initialize `mentions_while_offline = 0`.
    - For each offline interval `[start, end)` for user `i`:
      - Use binary search on the sorted `here_timestamps` to find how many timestamps fall within `[start, end)`.
      - Add this count to `mentions_while_offline`.
    - The number of `"HERE"` mentions while the user was online is `total_here_mentions - mentions_while_offline`. Add this to `mentions[i]`.
- **Return Result:** The `mentions` array now contains the final counts.

# Solutions
### Java

```java
class Solution {
public
  int[] countMentions(int numberOfUsers, List<List<String>> events) {
    events.sort((a, b)->{
      int x = Integer.parseInt(a.get(1));
      int y = Integer.parseInt(b.get(1));
      if (x == y) {
        return a.get(0).charAt(2) - b.get(0).charAt(2);
      }
      return x - y;
    });
    int[] ans = new int[numberOfUsers];
    int[] onlineT = new int[numberOfUsers];
    int lazy = 0;
    for (var e : events) {
      String etype = e.get(0);
      int cur = Integer.parseInt(e.get(1));
      String s = e.get(2);
      if (etype.charAt(0) == 'O') {
        onlineT[Integer.parseInt(s)] = cur + 60;
      } else if (s.charAt(0) == 'A') {
        ++lazy;
      } else if (s.charAt(0) == 'H') {
        for (int i = 0; i < numberOfUsers; ++i) {
          if (onlineT[i] <= cur) {
            ++ans[i];
          }
        }
      } else {
        for (var a : s.split(" ")) {
          ++ans[Integer.parseInt(a.substring(2))];
        }
      }
    }
    if (lazy > 0) {
      for (int i = 0; i < numberOfUsers; ++i) {
        ans[i] += lazy;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> countMentions(int numberOfUsers, vector<vector<string>> &events) {
    ranges ::sort(events, [](const vector<string> &a, const vector<string> &b) {
      int x = stoi(a[1]);
      int y = stoi(b[1]);
      if (x == y) {
        return a[0][2] < b[0][2];
      }
      return x < y;
    });
    vector<int> ans(numberOfUsers, 0);
    vector<int> onlineT(numberOfUsers, 0);
    int lazy = 0;
    for (const auto &e : events) {
      string etype = e[0];
      int cur = stoi(e[1]);
      string s = e[2];
      if (etype[0] == 'O') {
        onlineT[stoi(s)] = cur + 60;
      } else if (s[0] == 'A') {
        lazy++;
      } else if (s[0] == 'H') {
        for (int i = 0; i < numberOfUsers; ++i) {
          if (onlineT[i] <= cur) {
            ++ans[i];
          }
        }
      } else {
        stringstream ss(s);
        string token;
        while (ss >> token) {
          ans[stoi(token.substr(2))]++;
        }
      }
    }
    if (lazy > 0) {
      for (int i = 0; i < numberOfUsers; ++i) {
        ans[i] += lazy;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]: events . sort(key=lambda e: (int(e[1]), e[0][2])) ans = [0] * numberOfUsers online_t = [0] * numberOfUsers lazy = 0 for etype, ts, s in events: cur = int(ts) if etype[0] == "O": online_t[int(s)] = cur + 60 elif s[0] == "A": lazy += 1 elif s[0] == "H": for i, t in enumerate(online_t): if t <= cur: ans[i] += 1 else: for a in s . split(): ans[int(a[2:])] += 1 if lazy: for i in range(numberOfUsers): ans[i] += lazy return ans

```