#3433

Medium

LeetCode Problem Workspace

Count Mentions Per User

Calculate how many times each user is mentioned across MESSAGE events, accounting for offline and online statuses efficiently.

array math sorting simulation

Problem Statement

You are given an integer numberOfUsers representing the total number of users and an array events where each entry is a list of three elements: the type of event, the timestamp, and event-specific content. Each events[i] can either be a MESSAGE or an OFFLINE event. MESSAGE events list user ids mentioned or special keywords like ALL, while OFFLINE events indicate a user going offline at that timestamp.

Your task is to return an array mentions where mentions[i] represents the total number of times user i was mentioned across all MESSAGE events. Offline users do not count in mentions unless the MESSAGE contains ALL. Process events in chronological order and correctly handle array indexing and counting to match the expected per-user totals.

Examples

Example 1

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

Output: [2,2]

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]

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]

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.

Solution Approach

Sort Events by Timestamp

First, sort the events array by the timestamp field to ensure chronological handling. This step guarantees that offline and MESSAGE events are applied in the correct order, preventing miscounts of user mentions.

Track Online Status with Array

Maintain a boolean array representing each user's online status. For OFFLINE events, mark the corresponding user as offline. For MESSAGE events, check this array to decide which users are eligible to be mentioned, applying counting only to online users unless ALL is specified.

Count Mentions Using Array and Math Logic

Use an integer array to accumulate mention counts for each user. When a MESSAGE contains specific ids, increment the corresponding indexes. For keywords like ALL, increment every index using simple array iteration or vectorized addition. This approach combines array handling with arithmetic accumulation for efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * m) where n is the number of events and m is the number of user mentions per MESSAGE, due to iterating over users in messages. Sorting events by timestamp adds O(n log n). Space complexity is O(u) for arrays tracking online status and mention counts, where u is numberOfUsers.

What Interviewers Usually Probe

Mentions array should correctly reflect online filtering.
Sorting events before processing is a key optimization hint.
Handle special keywords like ALL carefully to avoid miscounting.

Common Pitfalls or Variants

Common pitfalls

Counting offline users during normal MESSAGE events.
Failing to sort events by timestamp before processing.
Incorrectly indexing users when mapping id strings to array positions.

Follow-up variants

MESSAGE events could include additional special keywords beyond ALL.
Users might toggle between online and offline multiple times per test case.
Events could arrive unsorted or with duplicate timestamps requiring stable processing.

FAQ

What is the most efficient way to track mentions per user in this problem?

Sort events by timestamp, maintain an array of online statuses, and increment a mentions array using simple math operations for each MESSAGE event.

How do OFFLINE events affect mention counts?

Users marked offline do not get their mention count incremented in normal MESSAGE events, but they are included if the MESSAGE contains the ALL keyword.

Why is sorting events necessary in Count Mentions Per User?

Sorting ensures that offline and MESSAGE events are applied chronologically, preventing overcounting or undercounting mentions due to ordering issues.

Can this problem handle up to 100 users efficiently?

Yes, using arrays for online status and mention counts scales linearly with the number of users, which is efficient for up to 100 users.

Does the pattern Array plus Math apply here?

Yes, the solution uses array structures to track online statuses and mention counts while applying arithmetic operations to accumulate mentions, following the Array plus Math pattern.

terminal

Solution

Solution 1: Sorting + Simulation

We sort the events in ascending order of timestamps. If the timestamps are the same, we place OFFLINE events before MESSAGE events.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Continue Practicing

#3428 maximum and minimum sums of at most size k subsequences #3382 maximum area rectangle with point constraints ii #3380 maximum area rectangle with point constraints i