3433. Count Mentions Per User
Approach
Sort events by time; process ALL/HERE offline tracking online users; sum mentions per user.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
Simulation problems require implementing the described process step by step. Focus on correctly handling edge cases and state transitions. Common in geometry, game problems, and string manipulation. Optimize only if the naive simulation exceeds the time limit.
// Approach: Sort events by time; process ALL/HERE offline tracking online users; sum mentions per user.
// Time: O(n log n) Space: O(n)
public class Solution
{
private record OfflineUser(int ReturnTimestamp, int UserId);
public int[] CountMentions(int numberOfUsers, IList<IList<string>> events)
{
int[] ans = new int[numberOfUsers];
bool[] online = new bool[numberOfUsers];
Array.Fill(online, true);
// min-heap to track users that are offline
var offlineQueue = new PriorityQueue<OfflineUser, int>();
int allMentionsCount = 0;
var sortedEvents = events.OrderBy(e => int.Parse(e[1]))
.ThenByDescending(e => e[0])
.ToList();
foreach (var eventItem in sortedEvents)
{
string eventType = eventItem[0];
int timestamp = int.Parse(eventItem[1]);
// Bring users back online if their offline period has ended.
while (offlineQueue.Count > 0 && offlineQueue.Peek().ReturnTimestamp <= timestamp)
{
var user = offlineQueue.Dequeue();
online[user.UserId] = true;
}
if (eventType == "MESSAGE")
{
string mentionsString = eventItem[2];
if (mentionsString == "ALL")
allMentionsCount++;
else if (mentionsString == "HERE")
{
for (int userId = 0; userId < numberOfUsers; ++userId)
{
if (online[userId])
ans[userId]++;
}
}
else
{
foreach (var userId in GetUserIds(mentionsString))
ans[userId]++;
}
}
else if (eventType == "OFFLINE")
{
int userId = int.Parse(eventItem[2]);
online[userId] = false;
// Add to queue to bring back online after 60 units
offlineQueue.Enqueue(new OfflineUser(timestamp + 60, userId), timestamp + 60);
}
}
// Add the "ALL" mentions to all users.
for (int userId = 0; userId < numberOfUsers; ++userId)
ans[userId] += allMentionsCount;
return ans;
}
private List<int> GetUserIds(string s)
{
var integers = new List<int>();
foreach (var part in s.Split(' '))
integers.Add(int.Parse(part.Substring(2)));
return integers;
}
}