Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Mentions depend on users' status at the event time, not the original event order. Store the time each offline user returns instead of scheduling separate return events. A user is online whenever that time is no later than the current timestamp.

Approach

Sort events by numeric timestamp, with OFFLINE events before messages at equal timestamps. Initialize mention counts to zero. An offline event sets that user's return time to the event time plus 60.

For an ALL message, increment every user. For HERE, increment only users whose return time is at most the message time, treating users never marked offline as online. Otherwise split the explicit mention tokens, extract each ID, and increment it regardless of online status. Repeated tokens count repeatedly.

The equal-time ordering ensures a newly offline user is excluded from HERE, while the inclusive return-time comparison makes a user online again exactly 60 time units later. Return the accumulated counts after all events.

class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        events.sort(key = lambda x: x[0], reverse = True)
        events.sort(key = lambda x: int(x[1]))
        mentions = [0] * numberOfUsers
        offline = defaultdict(int)

        for event, time, user in events:
            if event == 'OFFLINE':
                offline[int(user)] = int(time) + 60
            else:
                if user == 'ALL':
                    for u in range(numberOfUsers):
                        mentions[u] += 1
                elif user == 'HERE':
                    for u in range(numberOfUsers):
                        if offline[u] <= int(time):
                            mentions[u] += 1
                else:
                    curr = user.split()
                    for u in curr:
                        u = int(u[2:])
                        mentions[u] += 1

        return mentions

Complexity analysis

Let E be the number of events, U the user count, P the total explicit mention tokens, and L the maximum mention-string length. With the bounded ID and timestamp widths, Python takes O(E log(E+1) + EU + P) time. JavaScript additionally compares complete mention strings to break equal-time, equal-type ties, giving O(E log(E+1)(L+1) + EU + P) time as a conservative bound. Auxiliary space is O(E + U + L), including sorting and a message's split tokens. Under the stated 100-token cap, L is bounded, reducing these to the usual O(E log(E+1) + EU + P) time and O(E+U) space.