Count Mentions Per User
MedPrompt
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:
- Message Event:
["MESSAGE", "timestampi", "mentions_stringi"]- This event indicates that a set of users was mentioned in a message at
timestampi. - The
mentions_stringistring 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.
- This event indicates that a set of users was mentioned in a message at
- Offline Event:
["OFFLINE", "timestampi", "idi"]- This event indicates that the user
idihad become offline attimestampifor 60 time units. The user will automatically be online again at timetimestampi + 60.
- This event indicates that the user
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 <= 1001 <= events.length <= 100events[i].length == 3events[i][0]will be one ofMESSAGEorOFFLINE.1 <= int(events[i][1]) <= 105- The number of
id<number>mentions in any"MESSAGE"event is between1and100. 0 <= <number> <= numberOfUsers - 1- It is guaranteed that the user id referenced in the
OFFLINEevent is online at the time the event occurs.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Sort Events: Create a custom data structure for events or use a custom comparator to sort the input
eventsarray. The primary sorting key is the timestamp (integer value ofevents[i][1]). For ties in timestamp,OFFLINEevents should come beforeMESSAGEevents. - Initialize State:
mentions: An integer array of sizenumberOfUsers, initialized to all zeros. This will store the final counts.offlineUntil: An integer array of sizenumberOfUsers, initialized to all zeros.offlineUntil[i]will store the timestamp at which useribecomes online again. A useriis considered online at timetifofflineUntil[i] <= t.
- Iterate and Process: Loop through the sorted events. For each event at
currentTimestamp:- If it's an
OFFLINEevent foruserId:- Update the user's state:
offlineUntil[userId] = currentTimestamp + 60.
- Update the user's state:
- If it's a
MESSAGEevent:- Check the
mentions_string:"ALL": Iterate fromuser = 0tonumberOfUsers - 1and incrementmentions[user]."HERE": Iterate fromuser = 0tonumberOfUsers - 1. For each user, check if they are online atcurrentTimestamp(i.e.,offlineUntil[user] <= currentTimestamp). If they are, incrementmentions[user]."id<number> ...": Split the string by spaces. For each tokenid<number>, parse the<number>to get theuserIdand incrementmentions[userId]. No online check is needed for these direct mentions.
- Check the
- If it's an
- Return Result: After processing all events, the
mentionsarray holds the final counts.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
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
eventsarray once.- For
"id..."messages, parse the user IDs and directly increment their counts in thementionsarray. - For
"ALL"messages, incrementall_mention_count. - For
"HERE"messages, add the timestamp tohere_timestamps. - For
"OFFLINE"events for useriat timet, add the interval[t, t + 60)tooffline_intervals[i].
- For
- Initialize
- Apply "ALL" Mentions: Add
all_mention_countto every user's mention count. - Calculate "HERE" Mentions:
- Sort the
here_timestampslist. - The total number of
"HERE"messages istotal_here_mentions = here_timestamps.size(). - For each user
i:- Initialize
mentions_while_offline = 0. - For each offline interval
[start, end)for useri:- Use binary search on the sorted
here_timestampsto find how many timestamps fall within[start, end). - Add this count to
mentions_while_offline.
- Use binary search on the sorted
- The number of
"HERE"mentions while the user was online istotal_here_mentions - mentions_while_offline. Add this tomentions[i].
- Initialize
- Sort the
- Return Result: The
mentionsarray now contains the final counts.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.