LeetCode 3433 - Count Mentions Per User

This problem asks us to simulate a sequence of user activity events and count how many times each user is mentioned across all message events.

leetcodemediumarraymathsortingsimulation

LeetCode Problem 3433

Difficulty: 🟡 Medium
Topics: Array, Math, Sorting, Simulation

Solution

LeetCode 3433 - Count Mentions Per User

Problem Understanding

This problem asks us to simulate a sequence of user activity events and count how many times each user is mentioned across all message events.

We are given:

  • numberOfUsers, the total number of users with IDs from 0 to numberOfUsers - 1

  • events, where each event is either:

  • A message event that mentions users

  • An offline event that temporarily makes a user unavailable

The output should be an array mentions where mentions[i] is the total number of times user i was mentioned.

The challenge comes from the fact that user online status changes over time. Every user starts online. When an OFFLINE event occurs at timestamp t, that user becomes offline immediately and automatically returns online at timestamp t + 60.

Message events can contain three different mention formats:

  • idX mentions a specific user X
  • ALL mentions every user, including offline users
  • HERE mentions only users who are currently online

A particularly important rule is that status changes must be processed before messages at the same timestamp. This means that if a user comes back online at time t, they should be considered online for any message that also occurs at time t.

Another subtle detail is that explicit user mentions may contain duplicates. For example:

id2 id2 id2

mentions user 2 three separate times, so all three mentions must be counted.

Constraints Analysis

The constraints are very small:

  • At most 100 users
  • At most 100 events
  • At most 100 explicit mentions inside a message

Because both dimensions are tiny, efficiency is not a major concern. A straightforward simulation is sufficient.

Important Edge Cases

A few cases can easily cause mistakes:

  • A user returns online at exactly the same timestamp as a message.
  • Multiple offline periods may happen at different times for different users.
  • ALL includes offline users.
  • HERE excludes offline users.
  • Explicit idX mentions count even when the user is offline.
  • Duplicate IDs in a single message must all be counted.
  • Events may not be provided in the order required for processing equal timestamps.

The last point is especially important. Since status changes must happen before messages at the same timestamp, we should sort events appropriately before simulation.

Problem Understanding

The problem asks us to track how many times each user is mentioned in a series of events, given a total of numberOfUsers users. Each event can be either a MESSAGE event or an OFFLINE event. MESSAGE events specify users that are mentioned in a message, using either explicit IDs (id<number>), all users (ALL), or currently online users (HERE). OFFLINE events indicate that a user goes offline for exactly 60 time units.

The inputs are:

  • numberOfUsers: an integer specifying the total number of users, indexed from 0 to numberOfUsers - 1.
  • events: a list of lists, where each inner list has three elements [eventType, timestamp, payload].

The expected output is an array mentions of length numberOfUsers, where mentions[i] contains the total number of times user i was mentioned across all MESSAGE events. Users can be mentioned multiple times in a single message, and the offline/online status affects only the "HERE" token in MESSAGE events.

Constraints ensure that:

  1. All users are initially online.
  2. Users referenced in OFFLINE events are guaranteed to be online at that timestamp.
  3. Timestamps are integers up to 10^5.
  4. numberOfUsers and the number of events are small (≤ 100).

Edge cases that could trip up a naive implementation include:

  • Messages containing "HERE" when users are offline.
  • Messages containing duplicate IDs.
  • Users coming back online exactly at a timestamp coinciding with a MESSAGE event.
  • Multiple OFFLINE events affecting overlapping intervals.

Approaches

Brute Force

A brute force simulation would process events chronologically while maintaining the online/offline state of every user.

For every message:

  • If it is ALL, iterate through all users and increment their counts.
  • If it is HERE, iterate through all users and increment counts for online users.
  • If it contains explicit IDs, parse every token and increment the corresponding user's count.

To determine whether a user is online, we can track the timestamp when they become online again.

Since the maximum number of users and events is only 100, scanning all users whenever necessary is perfectly acceptable.

Key Insight

The only real difficulty is handling event ordering correctly.

The problem specifies:

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.

We can enforce this rule by sorting events using:

  1. Timestamp ascending
  2. OFFLINE before MESSAGE when timestamps are equal

Then, before processing each event at timestamp t, we update every user's status whose offline period has expired (returnTime <= t).

Once that is done, the current online set is always correct for processing HERE.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(E × U + M) O(U) Simulate every event and scan users when needed
Optimal O(E log E + E × U + M) O(U) Same simulation, but explicitly sorts events to guarantee correct timestamp handling

Where:

  • E = number of events
  • U = number of users
  • M = total number of explicit idX tokens across messages

Algorithm Walkthrough

  1. Create an array mentions of size numberOfUsers, initialized to zero.
  2. Create an array offlineUntil of size numberOfUsers.
  • offlineUntil[i] = 0 means the user is currently online.
  • If a user goes offline at time t, set offlineUntil[i] = t + 60.
  1. Sort all events by:
  • Timestamp ascending.
  • Event type priority, with OFFLINE before MESSAGE.
  1. Process events one by one in sorted order.
  2. Before handling the current event at timestamp t, scan all users:
  • If offlineUntil[user] <= t, mark the user as online by setting:
offlineUntil[user] = 0
  1. If the event is OFFLINE:
  • Extract the user ID.
  • Set:
offlineUntil[id] = t + 60
  1. If the event is a MESSAGE:

  • If the content is "ALL":

  • Increment every user's mention count.

  • If the content is "HERE":

  • Increment only users whose offlineUntil[user] == 0.

  • Otherwise:

  • Split the string by spaces.

  • For every token:

  • Extract the numeric portion after "id".

  • Increment that user's mention count.

  • Duplicates are naturally counted multiple times.

  1. After all events are processed, return mentions.

Why it works

At every event timestamp, all users whose offline period has expired are restored to online status before the event is processed. Sorting ensures offline transitions occur before messages at identical timestamps. Therefore, the online/offline state maintained by the simulation exactly matches the rules of the problem. Since every message type is counted according to its definition, the final mention totals are correct. The brute-force method would simulate time for each unit and track the online/offline status of each user. For every timestamp from the earliest to the latest, we would:

  1. Mark users offline or online according to events.
  2. Process MESSAGE events by scanning the mentions string and counting mentions according to online status.

This is correct but inefficient because the range of timestamps can be large (1 ≤ timestamp ≤ 10^5) while events.length ≤ 100, making scanning each time unit unnecessary.

Optimal

The key insight is that we do not need to simulate every timestamp, only the timestamps at which events occur. We can:

  1. Sort or process events in chronological order.
  2. Use a dictionary or array to track which users are currently offline.
  3. When processing a MESSAGE event:
  • "ALL" mentions every user regardless of status.
  • "HERE" mentions only users currently online.
  • Explicit id<number> mentions increment counts even if the user is offline.
  1. For OFFLINE events, we record both the start and the end of offline intervals to update online status before processing any message at the same timestamp.

This approach efficiently handles sparse timestamps and ensures correctness.

Approach Time Complexity Space Complexity Notes
Brute Force O(T * n) O(n) T = max timestamp, n = number of events; inefficient due to large T
Optimal O(n * k) O(u) n = number of events, k = max mentions per message, u = number of users; only process actual events

Algorithm Walkthrough

  1. Initialize an array mentions of length numberOfUsers with all zeros. This will hold the final counts.
  2. Initialize a set offline_until or an array of timestamps that tracks when each user comes back online. Initially, all users are online.
  3. Iterate through events in chronological order:

  • If an event is "OFFLINE" at timestamp t for user i:

  • Set offline_until[i] = t + 60. This represents when the user will automatically come back online.

  • If an event is "MESSAGE" at timestamp t with mentions_string:

  • First, check all users whose offline_until ≤ t and mark them as online.

  • Split the mentions_string by spaces and process each token:

  • "ALL": increment mentions[j] for all users j.

  • "HERE": increment mentions[j] for all users currently online.

  • "id<number>": increment mentions[number]. Duplicates count multiple times.

  1. Return the array mentions.

Why it works: At each step, the algorithm maintains the invariant that offline_until[i] > t iff user i is offline at timestamp t. By processing offline events first and then message events at the same timestamp, the online/offline status is always correct. Counting explicit IDs or "ALL"/"HERE" according to this status guarantees correct mention counts.

Python Solution

from typing import List

class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        events.sort(
            key=lambda e: (
                int(e[1]),
                0 if e[0] == "OFFLINE" else 1
            )
        )

        mentions = [0] * numberOfUsers
        offline_until = [0] * numberOfUsers

        for event_type, timestamp_str, value in events:
            timestamp = int(timestamp_str)

            for user in range(numberOfUsers):
                if offline_until[user] != 0 and offline_until[user] <= timestamp:
                    offline_until[user] = 0

            if event_type == "OFFLINE":
                user_id = int(value)
                offline_until[user_id] = timestamp + 60

            else:
                if value == "ALL":
                    for user in range(numberOfUsers):
                        mentions[user] += 1

                elif value == "HERE":
                    for user in range(numberOfUsers):
                        if offline_until[user] == 0:
                            mentions[user] += 1

                else:
                    for token in value.split():
        mentions = [0] * numberOfUsers
        offline_until = [0] * numberOfUsers  # timestamp when each user comes back online

        for event in sorted(events, key=lambda e: int(e[1])):
            etype, timestamp_str, payload = event
            timestamp = int(timestamp_str)

            # Update online status before processing the current event
            for i in range(numberOfUsers):
                if offline_until[i] <= timestamp:
                    offline_until[i] = 0  # mark as online

            if etype == "OFFLINE":
                user_id = int(payload)
                offline_until[user_id] = timestamp + 60
            elif etype == "MESSAGE":
                tokens = payload.split()
                for token in tokens:
                    if token == "ALL":
                        for i in range(numberOfUsers):
                            mentions[i] += 1
                    elif token == "HERE":
                        for i in range(numberOfUsers):
                            if offline_until[i] == 0:
                                mentions[i] += 1
                    elif token.startswith("id"):
                        user_id = int(token[2:])
                        mentions[user_id] += 1

        return mentions

The implementation begins by sorting events so that timestamps are processed chronologically and offline events take precedence over messages occurring at the same time.

The mentions array stores the final answer. The offline_until array stores when each user's offline period ends. A value of 0 means the user is currently online.

Before every event is processed, the code restores any users whose offline period has expired. This guarantees that the online state is always correct for the current timestamp.

For an OFFLINE event, the user is marked offline until timestamp + 60.

For a MESSAGE event, the code handles the three possible message formats independently:

  • ALL updates every user.
  • HERE updates only currently online users.
  • Explicit IDs are parsed individually and counted, including duplicates.

Finally, the completed mentions array is returned. The implementation sorts events by timestamp to ensure chronological order. The offline_until array efficiently tracks offline users, and "HERE" counts only currently online users, while "ALL" ignores status. Each token in a message is handled explicitly, supporting duplicates.

Go Solution

import (
	"sort"
	"strconv"
	"strings"
)

func countMentions(numberOfUsers int, events [][]string) []int {
	sort.Slice(events, func(i, j int) bool {
		ti, _ := strconv.Atoi(events[i][1])
		tj, _ := strconv.Atoi(events[j][1])

		if ti != tj {
			return ti < tj
		}

		if events[i][0] == events[j][0] {
			return false
		}

		return events[i][0] == "OFFLINE"
	})

	mentions := make([]int, numberOfUsers)
	offlineUntil := make([]int, numberOfUsers)

	for _, event := range events {
		eventType := event[0]
		timestamp, _ := strconv.Atoi(event[1])
		value := event[2]

		for user := 0; user < numberOfUsers; user++ {
			if offlineUntil[user] != 0 && offlineUntil[user] <= timestamp {
				offlineUntil[user] = 0
			}
		}

		if eventType == "OFFLINE" {
			userID, _ := strconv.Atoi(value)
			offlineUntil[userID] = timestamp + 60
		} else {
			if value == "ALL" {
				for user := 0; user < numberOfUsers; user++ {
					mentions[user]++
				}
			} else if value == "HERE" {
				for user := 0; user < numberOfUsers; user++ {
					if offlineUntil[user] == 0 {
						mentions[user]++
					}
				}
			} else {
				tokens := strings.Fields(value)

				for _, token := range tokens {
					userID, _ := strconv.Atoi(token[2:])
					mentions[userID]++
				}
			}
		}
	}

	return mentions
}

The Go implementation follows the exact same simulation strategy. The primary differences are:

  • sort.Slice is used for custom event ordering.
  • strconv.Atoi converts timestamps and user IDs from strings.
  • strings.Fields splits explicit mention lists.
  • Slices are used instead of Python lists.

No special overflow handling is required because all values remain well within Go's int range.

Worked Examples

Example 1

Input:

numberOfUsers = 2

[
 ["MESSAGE","10","id1 id0"],
 ["OFFLINE","11","0"],
 ["MESSAGE","71","HERE"]
]

After sorting:

Event Timestamp
MESSAGE id1 id0 10
OFFLINE 0 11
MESSAGE HERE 71

Initial state:

User offlineUntil mentions
0 0 0
1 0 0

Process message at 10:

User mentions
0 1
1 1

Process offline at 11:

User offlineUntil
0 71
1 0

Process timestamp 71:

User 0 returns online because offlineUntil == 71.

User offlineUntil
0 0
1 0

HERE mentions all online users:

User mentions
0 2
1 2

Answer:

[2, 2]

Example 2

Input:

[
 ["MESSAGE","10","id1 id0"],
 ["OFFLINE","11","0"],
 ["MESSAGE","12","ALL"]
]

After first message:

mentions = [1,1]

After offline:

offlineUntil = [71,0]

ALL mentions everyone, including offline users:

mentions = [2,2]

Answer:

[2,2]

Example 3

Input:

[
 ["OFFLINE","10","0"],
 ["MESSAGE","12","HERE"]
]

After offline:

offlineUntil = [70,0]

At timestamp 12:

user 0 offline
user 1 online

HERE only counts online users:

mentions = [0,1]

Answer:

[0,1]

Complexity Analysis

Measure Complexity Explanation
Time O(E log E + E × U + M) Sorting plus user scans and explicit mention processing
Space O(U) Mention counts and offline tracking arrays

The sorting step costs O(E log E). For every event we may scan all users to restore online status, costing O(E × U). Parsing explicit mentions contributes O(M), where M is the total number of mention tokens. Since the constraints are at most 100, this easily fits within limits.

Test Cases

from typing import List

s = Solution()

assert s.countMentions(
    2,
    [["MESSAGE","10","id1 id0"],
     ["OFFLINE","11","0"],
     ["MESSAGE","71","HERE"]]
) == [2, 2]  # official example 1

assert s.countMentions(
    2,
    [["MESSAGE","10","id1 id0"],
     ["OFFLINE","11","0"],
     ["MESSAGE","12","ALL"]]
) == [2, 2]  # official example 2

assert s.countMentions(
    2,
    [["OFFLINE","10","0"],
     ["MESSAGE","12","HERE"]]
) == [0, 1]  # official example 3

assert s.countMentions(
    1,
    [["MESSAGE","5","ALL"]]
) == [1]  # single user

assert s.countMentions(
    3,
    [["MESSAGE","1","id2 id2 id2"]]
) == [0, 0, 3]  # duplicate mentions count separately

assert s.countMentions(
    2,
    [["OFFLINE","10","0"],
     ["MESSAGE","70","HERE"]]
) == [1, 1]  # returns online exactly at timestamp 70

assert s.countMentions(
    2,
    [["MESSAGE","10","HERE"],
     ["OFFLINE","10","0"]]
) == [0, 1]  # same timestamp, offline processed first

assert s.countMentions(
    3,
    [["OFFLINE","5","1"],
     ["MESSAGE","6","ALL"]]
) == [1, 1, 1]  # ALL includes offline users

assert s.countMentions(
    3,
    [["OFFLINE","5","1"],
     ["MESSAGE","6","HERE"]]
) == [1, 0, 1]  # HERE excludes offline users

assert s.countMentions(
    3,
    [["MESSAGE","1","id0"],
     ["MESSAGE","2","id0 id1"],
     ["MESSAGE","3","id2"]]
) == [2, 1, 1]  # multiple explicit messages

Test Summary

Test Why
Example 1 User returns online exactly when message occurs
Example 2 ALL includes offline users
Example 3 HERE excludes offline users
Single user Smallest valid input
Duplicate IDs Multiple mentions counted separately
Return at timestamp Boundary condition for reactivation
Same timestamp ordering OFFLINE processed before MESSAGE
ALL with offline user Verifies ALL semantics
HERE with offline user Verifies HERE semantics
Multiple messages General counting correctness

Edge Cases

User Returns Online Exactly When a Message Occurs

A common mistake is treating a user as offline until after timestamp t + 60. The problem explicitly states that status changes happen before messages at the same timestamp. Therefore, if a user went offline at time 10, they are online again at time 70 and should be included in a HERE message at timestamp 70. The implementation handles this by restoring users whose offlineUntil <= currentTimestamp before processing the event.

Multiple Explicit Mentions of the Same User

A message such as:

id3 id3 id3

contains three separate mentions. Deduplicating IDs would produce an incorrect result. The implementation processes every token independently and increments the counter each time, preserving duplicates exactly as required.

OFFLINE and MESSAGE at the Same Timestamp

Suppose we have:

["OFFLINE","10","0"]
["MESSAGE","10","HERE"]

The user must be considered offline for that message. Sorting by timestamp alone is insufficient because the input order may place the message first. The implementation sorts events so that OFFLINE events are always processed before MESSAGE events at identical timestamps, guaranteeing correct behavior.

ALL Versus HERE

The two keywords have different semantics that are easy to confuse. ALL mentions every user regardless of status, while HERE only mentions users currently online. The implementation handles these cases in separate branches, ensuring offline users are included only when appropriate. func countMentions(numberOfUsers int, events [][]string) []int { mentions := make([]int, numberOfUsers) offlineUntil := make([]int, numberOfUsers)

// Sort events by timestamp
sort.Slice(events, func(i, j int) bool {
    ti, _ := strconv.Atoi(events[i][1])
    tj, _ := strconv.Atoi(events[j][1])
    return ti < tj
})

for _, event := range events {
    etype := event[0]
    timestamp, _ := strconv.Atoi(event[1])
    payload := event[2]

    // Update online status
    for i := 0; i < numberOfUsers; i++ {
        if offlineUntil[i] <= timestamp {
            offlineUntil[i] = 0
        }
    }

    if etype == "OFFLINE" {
        userID, _ := strconv.Atoi(payload)
        offlineUntil[userID] = timestamp + 60
    } else if etype == "MESSAGE" {
        tokens := strings.Fields(payload)
        for _, token := range tokens {
            if token == "ALL" {
                for i := 0; i < numberOfUsers; i++ {
                    mentions[i]++
                }
            } else if token == "HERE" {
                for i := 0; i < numberOfUsers; i++ {
                    if offlineUntil[i] == 0 {
                        mentions[i]++
                    }
                }
            } else if strings.HasPrefix(token, "id") {
                userID, _ := strconv.Atoi(token[2:])
                mentions[userID]++
            }
        }
    }
}
return mentions

}


Go differences: uses slices instead of lists, `strconv.Atoi` for string-to-int conversions, `strings.Fields` to split tokens. Sorting uses `sort.Slice`. Logic mirrors the Python version.

## Worked Examples

**Example 1**

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

| Timestamp | Event | Offline Users | Mentions |
| --- | --- | --- | --- |
| 10 | MESSAGE `"id1 id0"` | none | `[1,1]` |
| 11 | OFFLINE 0 | 0 | `[1,1]` |
| 71 | MESSAGE `"HERE"` | none (0 back online at 71) | `[2,2]` |

Output: `[2,2]`

**Example 2**

| Timestamp | Event | Offline Users | Mentions |
| --- | --- | --- | --- |
| 10 | MESSAGE `"id1 id0"` | none | `[1,1]` |
| 11 | OFFLINE 0 | 0 | `[1,1]` |
| 12 | MESSAGE `"ALL"` | 0 | `[2,2]` |

Output: `[2,2]`

**Example 3**

| Timestamp | Event | Offline Users | Mentions |
| --- | --- | --- | --- |
| 10 | OFFLINE 0 | 0 | `[0,0]` |
| 12 | MESSAGE `"HERE"` | 0 | `[0,1]` |

Output: `[0,1]`