3433. Count Mentions Per User

Problem Description

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:

Message Event: ["MESSAGE", "timestamp_i", "mentions_string_i"]
- This event indicates that a set of users was mentioned in a message at timestamp_i.
- The mentions_string_i string can contain one of the following tokens:
  - id<number>: where <number> 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", "timestamp_i", "id_i"]
- This event indicates that the user id_i had become offline at timestamp_i for 60 time units. The user will automatically be online again at time timestamp_i + 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.

Intuition

To tackle the problem, we need to simulate the timeline of events given, while maintaining the online/offline status of users and counting mentions accordingly. Here's a step-by-step breakdown of the approach:

Event Sorting: Start by sorting the events primarily by timestamp. If timestamps are equal, process OFFLINE events before MESSAGE events. This ensures that status updates always precede message handling at the same timestamp.
Simulation: Use an array, online_t, where online_t[i] records the next online time for the user i. This helps us track when a user who went offline will be back online.
Lazy Counting: Introduce a variable, lazy, to temporarily hold the count of ALL mentions until they are processed.
Event Handling: For each event:
- OFFLINE: Update the online_t to reflect the duration for which the user will be offline.
- MESSAGE with ALL: Increment the lazy variable as this represents a potential mention for all users.
- MESSAGE with HERE: Check the online_t array and increment mentions for those users whose next online time is less than or equal to the current time.
- Specific Message Mentions: Directly increment mentions for specified users from the mentions_string.
Final Mention Count: After processing, if lazy is non-zero, add this count to all users' mentions, thus completing the processing of ALL events.

This approach efficiently combines sorting and event simulation to derive the final mentioned counts.

Learn more about Math and Sorting patterns.

Solution Approach

The approach to solving this problem involves sorting the events and simulating the change in user status over time. Here's how it is implemented:

Sorting the Events:
- First, sort all the events by timestamp. If two events have the same timestamp, prioritize OFFLINE events before MESSAGE events. This ensures that users’ status changes are processed before counting mentions in messages occurring at the same time.
Tracking User Status:
- Use an array online_t where online_t[i] represents the earliest timestamp when user i will be back online after going offline. Initially, all elements are set to 0 since all users start as online.
Simulating the Events:
- Iterate through each sorted event. For each event:
  - OFFLINE Event: Update the online_t to timestamp + 60 for the user going offline, indicating the time when they will come back online automatically.
  - MESSAGE Event:
    - If the event mentions ALL, increment a lazy counter for later use.
    - If mentioning HERE, iterate through online_t. For each user, if their online_t value is less than or equal to the current timestamp, increment their mention count in the result.
    - For specific user mentions (id<n>), directly increment their count in the result.
Applying Lazy Updates:
- After processing all events, if the lazy counter is greater than zero, apply its value to each user's mention count. This accounts for the delayed mention counts from ALL events that applied to all users.
Final Result:
- Return the mentions array, which contains the total count of mentions each user received.

This method efficiently handles real-time user status updates and cumulative message mentions using sorting and simulation. It optimizes the handling of events to ensure correct mention counting under varying online/offline conditions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example with numberOfUsers = 3 and the following events array:

[
  ["MESSAGE", 1, "id0 id1 ALL"],
  ["OFFLINE", 2, "0"],
  ["MESSAGE", 3, "HERE"],
  ["OFFLINE", 4, "1"],
  ["MESSAGE", 5, "id1 ALL"]
]

Step-by-Step Execution:

Sort Events by Timestamp:

The sorted list of events is:

[
  ["MESSAGE", 1, "id0 id1 ALL"],
  ["OFFLINE", 2, "0"],
  ["MESSAGE", 3, "HERE"],
  ["OFFLINE", 4, "1"],
  ["MESSAGE", 5, "id1 ALL"]
]

Initialize Data Structures:
- online_t: [0, 0, 0] (all users start online).
- mentions: [0, 0, 0] (initial mention count for users 0, 1, 2).
- lazy: 0 (counter for potential "ALL" mentions).
Process Each Event:
- Event 1: ["MESSAGE", 1, "id0 id1 ALL"]
  - Mentions id0: 1 for user 0.
  - Mentions id1: 1 for user 1.
  - Mentions ALL: Increment lazy by 1.
- Event 2: ["OFFLINE", 2, "0"]
  - User 0 goes offline. Update online_t[0] = 62.
- Event 3: ["MESSAGE", 3, "HERE"]
  - User 0 offline (online_t[0] = 62), not counted.
  - User 1 online (online_t[1] = 0): 1 for user 1.
  - User 2 online (online_t[2] = 0): 1 for user 2.
- Event 4: ["OFFLINE", 4, "1"]
  - User 1 goes offline. Update online_t[1] = 64.
- Event 5: ["MESSAGE", 5, "id1 ALL"]
  - Mentions id1: 1 for user 1 (still counts even when offline).
  - Mentions ALL: Increment lazy by 1.
Apply Lazy Updates:

After processing all events, lazy = 2. Apply this to each user's mention count:
- User 0: 2 + 1 (initial) = 3
- User 1: 3 (initial) + 2 = 5
- User 2: 1 (initial) + 2 = 3
Final Mentions Array:

Therefore, the final mentions array is [3, 5, 3].

This walkthrough illustrates the sequence of processing events, update mechanics, and cumulative counting of mentions to demonstrate the solution approach.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
5        # Sort events by timestamp first, then by user index (if applicable)
6        events.sort(key=lambda e: (int(e[1]), e[0][2]))
7      
8        # Initialize a list to store the mentions count for each user
9        mentions_count = [0] * numberOfUsers
10      
11        # Initialize a list to keep track of "online" timestamp for each user
12        online_until = [0] * numberOfUsers
13      
14        # Variable to account for "lazy" count (number of "Add" operations)
15        lazy_addition = 0
16      
17        # Iterate through each event
18        for event_type, timestamp, users_info in events:
19            current_time = int(timestamp)
20          
21            # Handle "Online" event
22            if event_type[0] == "O":
23                # Set the time until the user is considered online
24                online_until[int(users_info)] = current_time + 60
25          
26            # Handle "Add" event
27            elif users_info[0] == "A":
28                # Increment lazy count since no direct mention happens
29                lazy_addition += 1
30          
31            # Handle "Harvest" event
32            elif users_info[0] == "H":
33                # Check each user's online status at the current time
34                for i, online_time in enumerate(online_until):
35                    if online_time <= current_time:
36                        mentions_count[i] += 1
37
38            # Handle direct mention events (e.g., "Mention user")
39            else:
40                # Parse users_info to get the mentioned user indices
41                for user_str in users_info.split():
42                    user_index = int(user_str[2:])
43                    mentions_count[user_index] += 1
44      
45        # Apply lazy addition to all users if any "Add" event occurred
46        if lazy_addition:
47            for i in range(numberOfUsers):
48                mentions_count[i] += lazy_addition
49      
50        return mentions_count
51

1class Solution {
2    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
3        // Sort events primarily by time and secondarily by the third character of the event type
4        events.sort((event1, event2) -> {
5            int time1 = Integer.parseInt(event1.get(1));
6            int time2 = Integer.parseInt(event2.get(1));
7            if (time1 == time2) {
8                // Compare the third character of event types if times are the same
9                return event1.get(0).charAt(2) - event2.get(0).charAt(2);
10            }
11            return time1 - time2;
12        });
13
14        int[] mentionCounts = new int[numberOfUsers]; // Array to hold the mention counts for each user
15        int[] onlineTimes = new int[numberOfUsers]; // Array to track when each user is online
16        int lazyMentions = 0; // Counter for the number of lazy mentions
17
18        // Iterate over each event
19        for (var event : events) {
20            String eventType = event.get(0);
21            int currentTime = Integer.parseInt(event.get(1));
22            String details = event.get(2);
23
24            // Handle 'online' event: Update the online expiration time for the specified user
25            if (eventType.charAt(0) == 'O') {
26                onlineTimes[Integer.parseInt(details)] = currentTime + 60;
27
28            // Handle 'all' event: Increase the lazy count for all users
29            } else if (details.charAt(0) == 'A') {
30                lazyMentions++;
31          
32            // Handle 'heartbeat' event: Count mentions for users who are offline
33            } else if (details.charAt(0) == 'H') {
34                for (int i = 0; i < numberOfUsers; ++i) {
35                    if (onlineTimes[i] <= currentTime) {
36                        mentionCounts[i]++;
37                    }
38                }
39
40            // Handle mentions directed to specific users
41            } else {
42                // Split the user mention details and increment their mention count
43                for (var mention : details.split(" ")) {
44                    mentionCounts[Integer.parseInt(mention.substring(2))]++;
45                }
46            }
47        }
48
49        // If there were any lazy mentions, add them to each user's mention count
50        if (lazyMentions > 0) {
51            for (int i = 0; i < numberOfUsers; ++i) {
52                mentionCounts[i] += lazyMentions;
53            }
54        }
55
56        return mentionCounts;
57    }
58}
59

1#include <vector>
2#include <string>
3#include <sstream>
4#include <algorithm>
5#include <ranges>
6
7using namespace std;
8
9class Solution {
10public:
11    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
12        // Sort events firstly by the timestamp (index 1), then by the user ID (index 0, third character)
13        ranges::sort(events, [](const vector<string>& a, const vector<string>& b) {
14            int timestampA = stoi(a[1]);
15            int timestampB = stoi(b[1]);
16            if (timestampA == timestampB) {
17                return a[0][2] < b[0][2];
18            }
19            return timestampA < timestampB;
20        });
21
22        // Initialize vectors to store the number of mentions and online status for each user
23        vector<int> mentionsCount(numberOfUsers, 0);
24        vector<int> onlineTime(numberOfUsers, 0);
25        int lazyEvents = 0; // Track the number of lazy events
26      
27        // Iterate over the events
28        for (const auto& event : events) {
29            string eventType = event[0]; // Type of event
30            int currentTime = stoi(event[1]); // Current time from the event
31            string data = event[2]; // Data associated with the event
32
33            if (eventType[0] == 'O') {
34                // 'O' indicates an online event, update online time for the user
35                onlineTime[stoi(data)] = currentTime + 60; // Assume online for the next 60 units
36            } 
37            else if (data[0] == 'A') {
38                // 'A' as first character of data implies a lazy event; increment lazy counter
39                lazyEvents++;
40            } 
41            else if (data[0] == 'H') {
42                // 'H' implies a help request; check mentions count for users that are expired
43                for (int i = 0; i < numberOfUsers; ++i) {
44                    if (onlineTime[i] <= currentTime) {
45                        ++mentionsCount[i]; // Increment if user is considered online
46                    }
47                }
48            } 
49            else {
50                // Mentions from other users, indicated by user IDs in the string data
51                stringstream ss(data);
52                string token;
53                while (ss >> token) {
54                    mentionsCount[stoi(token.substr(2))]++; // Increment mention count for each user ID found
55                }
56            }
57        }
58
59        // If there are lazy events, add them to each user's mention count
60        if (lazyEvents > 0) {
61            for (int i = 0; i < numberOfUsers; ++i) {
62                mentionsCount[i] += lazyEvents;
63            }
64        }
65
66        return mentionsCount; // Return the final mentions counts for each user
67    }
68};
69

1/**
2 * Function to count the number of mentions for each user.
3 * @param numberOfUsers - Total number of users.
4 * @param events - Array of events containing event type, timestamp, and involved users or actions.
5 * @returns Array representing the count of mentions for each user.
6 */
7function countMentions(numberOfUsers: number, events: string[][]): number[] {
8    // Sort events based on timestamp and a secondary condition on event type, if timestamps are equal
9    events.sort((a, b) => {
10        const firstTimestamp = +a[1];
11        const secondTimestamp = +b[1];
12
13        // If timestamps are the same, sort by third character of event type
14        if (firstTimestamp === secondTimestamp) {
15            return a[0].charAt(2) < b[0].charAt(2) ? -1 : 1;
16        }
17
18        return firstTimestamp - secondTimestamp;
19    });
20
21    // Array to hold the count of mentions for each user, initialized to 0
22    const mentionsCount: number[] = Array(numberOfUsers).fill(0);
23
24    // Array to track online users with the time they come online
25    const onlineUntil: number[] = Array(numberOfUsers).fill(0);
26
27    // Counter for lazy mentions indicated by 'A'
28    let lazyMentions = 0;
29
30    // Process each event
31    for (const [eventType, timestamp, usersOrAction] of events) {
32        const currentTime = +timestamp;
33
34        // Handle 'Online' event
35        if (eventType.charAt(0) === 'O') {
36            const userID = +usersOrAction;
37            onlineUntil[userID] = currentTime + 60; // Mark the user as online for 60 more seconds
38
39        // Handle 'All action' event
40        } else if (usersOrAction.charAt(0) === 'A') {
41            lazyMentions++;
42
43        // Handle 'Highlight' event
44        } else if (usersOrAction.charAt(0) === 'H') {
45            // Increment mentions for all offline users
46            for (let i = 0; i < numberOfUsers; i++) {
47                if (onlineUntil[i] <= currentTime) {
48                    mentionsCount[i]++;
49                }
50            }
51      
52        // Handle specific mentions
53        } else {
54            const mentions = usersOrAction.split(' ');
55            for (const mention of mentions) {
56                const userID = +mention.slice(2);
57                mentionsCount[userID]++;
58            }
59        }
60    }
61
62    // Add lazy mentions to all users if any exists
63    if (lazyMentions > 0) {
64        for (let i = 0; i < numberOfUsers; i++) {
65            mentionsCount[i] += lazyMentions;
66        }
67    }
68
69    return mentionsCount;
70}
71

Time and Space Complexity

The code iterates over the events list which takes O(m), where m is the number of events. Sorting the events by timestamp and some string operation takes O(m \log m \log M) time complexity, assuming string comparisons take O(\log M) time due to the substring operation. The nested loop iterating over online_t during the "H" type event processing takes O(n \times m), where n is the number of users. The calculation of mentions through lazy addition at the end takes O(n). Combining these gives the total time complexity as O(m \log m \log M + n \times m + n).

Space complexity is mainly dictated by the ans and online_t arrays, each of size n, leading to a space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don't know