In this guide, you will get 3433. Count Mentions Per User LeetCode Solution with the best time and space complexity. The solution to Count Mentions Per User 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.
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:
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: where 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.
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.
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 mentions in any “MESSAGE” event is between 1 and 100.
0 <= <= numberOfUsers – 1
It is guaranteed that the user id referenced in the OFFLINE event is online at the time the event occurs.
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
3433. Count Mentions Per User LeetCode Solution in C++
struct OfflineUser {
int returnTimestamp;
int userId;
bool operator>(const OfflineUser& other) const {
return returnTimestamp > other.returnTimestamp;
}
};
class Solution {
public:
vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
vector<int> ans(numberOfUsers);
vector<int> online(numberOfUsers, true);
// min-heap to track users that are offline
priority_queue<OfflineUser, vector<OfflineUser>, greater<>> offlineQueue;
int allMentionsCount = 0;
ranges::sort(events, [](const vector<string>& a, const vector<string>& b) {
const int timestampA = stoi(a[1]);
const int timestampB = stoi(b[1]);
return timestampA == timestampB ? a[0] > b[0] : timestampA < timestampB;
});
for (const vector<string>& event : events) {
const string eventType = event[0];
const int timestamp = stoi(event[1]);
// Bring users back online if their offline period has ended.
while (!offlineQueue.empty() &&
offlineQueue.top().returnTimestamp <= timestamp)
online[offlineQueue.top().userId] = true, offlineQueue.pop();
if (eventType == "MESSAGE") {
const string mentionsString = event[2];
if (mentionsString == "ALL") {
++allMentionsCount;
} else if (mentionsString == "HERE") {
for (int userId = 0; userId < numberOfUsers; ++userId)
if (online[userId])
++ans[userId];
} else {
for (const int userId : getUserIds(mentionsString))
++ans[userId];
}
} else if (eventType == "OFFLINE") {
const int userId = stoi(event[2]);
online[userId] = false;
// Add to queue to bring back online after 60 units.
offlineQueue.emplace(timestamp + 60, userId);
}
}
// Add the "ALL" mentions to all users.
for (int userId = 0; userId < numberOfUsers; ++userId)
ans[userId] += allMentionsCount;
return ans;
}
private:
vector<int> getUserIds(const string& s) {
vector<int> integers;
istringstream iss(s);
for (string id; iss >> id;)
integers.push_back(stoi(id.substr(2)));
return integers;
}
}; /* code provided by PROGIEZ */
3433. Count Mentions Per User LeetCode Solution in Java
class OfflineUser {
public int returnTimestamp;
public int userId;
public OfflineUser(int returnTimestamp, int userId) {
this.returnTimestamp = returnTimestamp;
this.userId = userId;
}
public static Comparator<OfflineUser> comparator = new Comparator<OfflineUser>() {
@Override
public int compare(OfflineUser o1, OfflineUser o2) {
return Integer.compare(o1.returnTimestamp, o2.returnTimestamp);
}
};
}
class Solution {
public int[] countMentions(int numberOfUsers, List<List<String>> events) {
int[] ans = new int[numberOfUsers];
boolean[] online = new boolean[numberOfUsers];
Arrays.fill(online, true);
// min-heap to track users that are offline
Queue<OfflineUser> offlineQueue = new PriorityQueue<>(OfflineUser.comparator);
int allMentionsCount = 0;
events.sort((a, b) -> {
final int timestampA = Integer.parseInt(a.get(1));
final int timestampB = Integer.parseInt(b.get(1));
return timestampA == timestampB ? b.get(0).compareTo(a.get(0))
: Integer.compare(timestampA, timestampB);
});
for (List<String> event : events) {
final String eventType = event.get(0);
final int timestamp = Integer.parseInt(event.get(1));
// Bring users back online if their offline period has ended.
while (!offlineQueue.isEmpty() && offlineQueue.peek().returnTimestamp <= timestamp)
online[offlineQueue.poll().userId] = true;
if (eventType.equals("MESSAGE")) {
String mentionsString = event.get(2);
if (mentionsString.equals("ALL")) {
++allMentionsCount;
} else if (mentionsString.equals("HERE")) {
for (int userId = 0; userId < numberOfUsers; ++userId)
if (online[userId])
++ans[userId];
} else {
for (final int userId : getUserIds(mentionsString))
++ans[userId];
}
} else if (eventType.equals("OFFLINE")) {
final int userId = Integer.parseInt(event.get(2));
online[userId] = false;
// Add to queue to bring back online after 60 units
offlineQueue.offer(new OfflineUser(timestamp + 60, userId));
}
}
// Add the "ALL" mentions to all users.
for (int userId = 0; userId < numberOfUsers; ++userId)
ans[userId] += allMentionsCount;
return ans;
}
private List<Integer> getUserIds(final String s) {
List<Integer> integers = new ArrayList<>();
for (String part : s.split(" "))
integers.add(Integer.parseInt(part.substring(2)));
return integers;
}
} // code provided by PROGIEZ
3433. Count Mentions Per User LeetCode Solution in Python
from dataclasses import dataclass
@dataclass(frozen=True)
class OfflineUser:
returnTimestamp: int
userId: int
def __lt__(self, other):
return self.returnTimestamp < other.returnTimestamp
class Solution:
def countMentions(
self,
numberOfUsers: int,
events: list[list[str]]
) -> list[int]:
ans = [0] * numberOfUsers
online = [True] * numberOfUsers
offlineQueue = [] # min-heap to track users that are offline
allMentionsCount = 0
events.sort(key=lambda x: (int(x[1]), -ord(x[0][0])))
for eventType, t, messageContent in events:
timestamp = int(t)
# Bring users back online if their offline period has ended.
while offlineQueue and offlineQueue[0].returnTimestamp <= timestamp:
user = heapq.heappop(offlineQueue)
online[user.userId] = True
if eventType == "MESSAGE":
match messageContent:
case "ALL":
allMentionsCount += 1
case "HERE":
for userId in range(numberOfUsers):
if online[userId]:
ans[userId] += 1
case _:
for userId in [int(part[2:]) for part in messageContent.split()]:
ans[userId] += 1
elif eventType == "OFFLINE":
userId = int(messageContent)
online[userId] = False
# Add to queue to bring back online after 60 units.
heapq.heappush(offlineQueue, OfflineUser(timestamp + 60, userId))
# Add the "ALL" mentions to all users.
for userId in range(numberOfUsers):
ans[userId] += allMentionsCount
return ans # code by PROGIEZ
