Count Mentions Per User - Practice Coding Problems

Count Mentions Per User - Problem

You are given an integer numberOfUsers representing the total number of users and an array events of size n × 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.

Input & Output

Example 1 — Basic Message and Offline Events

$ Input: numberOfUsers = 3, events = [["MESSAGE","1","id0 id1"],["OFFLINE","2","1"],["MESSAGE","3","HERE"]]

› Output: [2,1,1]

💡 Note: First message mentions users 0 and 1. User 1 goes offline at t=2. Second message at t=3 uses HERE (mentions online users only: 0 and 2). Final counts: user 0 gets 2 mentions, user 1 gets 1 mention, user 2 gets 1 mention.

Example 2 — ALL Mentions

$ Input: numberOfUsers = 2, events = [["MESSAGE","5","ALL"],["OFFLINE","10","0"],["MESSAGE","15","ALL"]]

› Output: [2,2]

💡 Note: First ALL mentions both users. User 0 goes offline. Second ALL still mentions ALL users (even offline ones). Both users get 2 mentions each.

Example 3 — Duplicate Mentions

$ Input: numberOfUsers = 2, events = [["MESSAGE","1","id0 id0 id1"]]

› Output: [2,1]

💡 Note: User 0 is mentioned twice in the same message (duplicates count separately), user 1 is mentioned once.

Constraints

1 ≤ numberOfUsers ≤ 1000
1 ≤ events.length ≤ 1000
0 ≤ timestamp_i ≤ 10⁹
Each mention string contains valid tokens only

Visualization

Tap to expand

Understanding the Visualization

Input

Events with timestamps, message mentions, and offline periods

Process

Handle events chronologically, track user status

Output

Array with mention count per user

Key Takeaway

🎯 Key Insight: Process events chronologically while efficiently tracking user online/offline status to handle HERE mentions correctly

Asked in

M Meta 35 a Amazon 28 G Google 22 M Microsoft 18

The key insight is to process events chronologically while tracking user online/offline status efficiently. Sort events by timestamp, then for each message event, parse the mention string to handle individual IDs, ALL (all users), and HERE (online users only). Best approach uses timeline-based offline tracking: Time: O(n log n + m), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Event Processing	O(n log n + m)	O(n)	Process events chronologically, tracking user online status and counting mentions
Optimized Event Processing with Timeline	O(n log n + m)	O(n)	Efficiently track offline periods and process events with better time complexity

Brute Force Event Processing — Algorithm Steps

Step 1: Sort events by timestamp to ensure chronological processing
Step 2: Track online status for each user (initially all online)
Step 3: For each event, update offline status or count mentions based on event type
Step 4: Parse mention strings to handle id<number>, ALL, and HERE tokens

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Events

Order events by timestamp

Process Events

Handle offline and message events

Count Mentions

Track mentions per user

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* solution(int numberOfUsers, char events[][3][100], int eventsSize) {
    int* mentions = (int*)calloc(numberOfUsers, sizeof(int));
    bool* online = (bool*)malloc(numberOfUsers * sizeof(bool));
    
    // Initialize all users as online
    for (int i = 0; i < numberOfUsers; i++) {
        online[i] = true;
    }
    
    // Process events (assuming they are sorted)
    for (int i = 0; i < eventsSize; i++) {
        char* eventType = events[i][0];
        
        if (strcmp(eventType, "OFFLINE") == 0) {
            int userId = atoi(events[i][2]);
            online[userId] = false;
        } else if (strcmp(eventType, "MESSAGE") == 0) {
            char* mentionString = events[i][2];
            
            if (strcmp(mentionString, "ALL") == 0) {
                for (int j = 0; j < numberOfUsers; j++) {
                    mentions[j]++;
                }
            } else if (strcmp(mentionString, "HERE") == 0) {
                for (int j = 0; j < numberOfUsers; j++) {
                    if (online[j]) {
                        mentions[j]++;
                    }
                }
            } else {
                // Parse individual mentions
                char* token = strtok(mentionString, " ");
                while (token != NULL) {
                    if (strncmp(token, "id", 2) == 0) {
                        int userId = atoi(token + 2);
                        mentions[userId]++;
                    }
                    token = strtok(NULL, " ");
                }
            }
        }
    }
    
    free(online);
    return mentions;
}

int main() {
    int numberOfUsers;
    scanf("%d", &numberOfUsers);
    
    // Simplified input parsing
    char events[1000][3][100];
    int eventsSize = 0;
    
    int* result = solution(numberOfUsers, events, eventsSize);
    
    printf("[");
    for (int i = 0; i < numberOfUsers; i++) {
        printf("%d", result[i]);
        if (i < numberOfUsers - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m)

Sorting events takes O(n log n), parsing mention strings takes O(m) where m is total length of all mention strings

⚡ Linearithmic

Space Complexity

O(n)

Array to track online status for n users plus space for mentions count array

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Event Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler