Skip to main content

Count Mentions Per User | Leetcode | Problem Explanation and Solution Approaches

Tracking mentions in messages is a common task in communication-based applications. This blog post breaks down a complex problem, "Count Mentions Per User," and walks through how to solve it efficiently with a clear understanding of all rules and constraints.

Problem Statement

You are given:

  1. An integer numberOfUsers representing the total number of users.

  2. An array events where each element is of size n x 3 and describes either a "MESSAGE" or an "OFFLINE" event.

Each event can be one of the following types:

  1. MESSAGE Event: ["MESSAGE", "timestamp", "mentions_string"]

    • Indicates that users are mentioned in a message at a specific timestamp.

    • The mentions_string can contain:

      • id<number>: Mentions a specific user (e.g., id0, id1).

      • ALL: Mentions all users (online or offline).

      • HERE: Mentions only users who are online at the time.

  2. OFFLINE Event: ["OFFLINE", "timestamp", "id<number>"]

    • Indicates that a user has gone offline for 60 time units. They automatically come back online at timestamp + 60.

Your task is to calculate the total mentions for each user across all events. The result should be an array mentions where mentions[i] represents the number of times user i is mentioned.

Constraints

  1. All users are initially online.

  2. Offline/online status changes are processed before any MESSAGE event at the same timestamp.

  3. A user can be mentioned multiple times in a single message, and all mentions are counted.

  4. Constraints:

    • 1 <= numberOfUsers <= 100

    • 1 <= events.length <= 100

    • 1 <= int(events[i][1]) <= 10^5

    • mentions_string may contain up to 100 tokens.

Example 1:

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

Explanation:

  • 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 only online users (id0 and id1) are mentioned by HERE. Mentions = [2, 2].

Example 2:

Input: numberOfUsers = 3, events = [
    ["MESSAGE", "2", "HERE"],
    ["OFFLINE", "2", "1"],
    ["OFFLINE", "1", "0"],
    ["MESSAGE", "61", "HERE"]
]
Output: [1, 0, 2]

Explanation:

  • At timestamp 1, id0 goes offline.

  • At timestamp 2, id1 goes offline, and HERE mentions only online users (id2). Mentions = [0, 0, 1].

  • At timestamp 61, id0 comes back online, and HERE mentions online users (id0 and id2). Mentions = [1, 0, 2].

Approach to Solve the Problem

Key Observations:

  1. Offline and online transitions must be applied before processing any MESSAGE events at the same timestamp.

  2. Use a sorted order of events to ensure proper sequencing.

  3. Maintain an array for online status and a map for tracking when users come back online.

Steps to Solve:

  1. Sort Events:

    • Sort the events array by timestamp.

    • This ensures offline/online transitions are processed before any MESSAGE events with the same timestamp.

  2. Online Status Update:

    • Use a map to track the timestamp when each offline user comes back online.

    • Before processing an event, check if any user’s offline period has ended.

  3. Process Events:

    • For OFFLINE events:

      • Mark the user as offline and add their return time to the map.

    • For MESSAGE events:

      • Handle mentions based on the type of mentions_string (“ALL”, “HERE”, or id<number>).

Code Implementation

#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <sstream>
using namespace std;

struct OnlineEvent {
    int timestamp;
    int user_id;
};

struct CompareOnlineEvent {
    bool operator()(const OnlineEvent& a, const OnlineEvent& b) const {
        return a.timestamp > b.timestamp;
    }
};

class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        // Sort events based on timestamp
        sort(events.begin(), events.end(), [&](const vector<string>& a, const vector<string>& b) -> bool {
            return stoi(a[1]) < stoi(b[1]);
        });

        // Initialize mentions and online status arrays
        vector<int> mentions(numberOfUsers, 0);
        vector<bool> online(numberOfUsers, true);

        // Priority queue to manage users coming online
        priority_queue<OnlineEvent, vector<OnlineEvent>, CompareOnlineEvent> online_heap;
       
        int n = events.size();
        int i = 0;
       
        // Process each event
        while (i < n) {
            int current_t = stoi(events[i][1]);

            // Process users who should be online by the current timestamp
            while (!online_heap.empty() && online_heap.top().timestamp <= current_t) {
                int user_to_online = online_heap.top().user_id;
                if (user_to_online >= 0 && user_to_online < numberOfUsers) {
                    online[user_to_online] = true;
                }
                online_heap.pop();
            }

            int j = i;
            // Group all events with the same timestamp together
            while (j < n && stoi(events[j][1]) == current_t) {
                j++;
            }

            // Handle "OFFLINE" events
            for (int k = i; k < j; ++k) {
                if (events[k][0] == "OFFLINE") {
                    int user_id = stoi(events[k][2]);
                    if (user_id >= 0 && user_id < numberOfUsers && online[user_id]) {
                        online[user_id] = false;
                        OnlineEvent oe;
                        oe.timestamp = current_t + 60;  // User comes online after 60 seconds
                        oe.user_id = user_id;
                        online_heap.push(oe);
                    }
                }
            }

            // Handle "MESSAGE" events
            for (int k = i; k < j; ++k) {
                if (events[k][0] == "MESSAGE") {
                    string mentions_string = events[k][2];
                   
                    // Handle "ALL" mentions
                    if (mentions_string == "ALL") {
                        for (int u = 0; u < numberOfUsers; ++u) {
                            mentions[u]++;
                        }
                    }
                    // Handle "HERE" mentions
                    else if (mentions_string == "HERE") {
                        for (int u = 0; u < numberOfUsers; ++u) {
                            if (online[u]) {
                                mentions[u]++;
                            }
                        }
                    }
                    // Handle specific user mentions
                    else {
                        stringstream ss(mentions_string);
                        string token;
                        while (ss >> token) {
                            if (token.size() >= 3 && token.substr(0, 2) == "id") {
                                string id_str = token.substr(2);
                                bool valid = true;
                                for (char c : id_str) {
                                    if (!isdigit(c)) {
                                        valid = false;
                                        break;
                                    }
                                }
                                if (valid) {
                                    int user_id = stoi(id_str);
                                    if (user_id >= 0 && user_id < numberOfUsers) {
                                        mentions[user_id]++;
                                    }
                                }
                            }
                        }
                    }
                }
            }

            // Move to the next set of events with a different timestamp
            i = j;
        }
       
        return mentions;
    }
};

Complexity Analysis

  1. Time Complexity:

    • Sorting the events: , where is the number of events.

    • Processing each event: , where is the average number of tokens in a MESSAGE.

    • Total: .

  2. Space Complexity:

    • , where is the number of users (for online and offlineEndTime).

Popular posts from this blog

Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that: One of the characters has an even frequency . The other character has an odd frequency . The difference is calculated as:  odd_frequency - even_frequency We need to return the maximum possible difference between the odd and even frequencies. Example Walkthrough Let's take a couple of examples to better understand the problem: Example 1: Input:  s = "aaaaabbc" Frequencies: 'a' → 5 (odd) 'b' → 2 (even) 'c' → 1 (odd) Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is: maxOdd - maxEven = 5 - 2 = 3 Example 2: Input:  s = "abcabcab" Frequencies: 'a' → 3 (odd) 'b' → 2 (even) 'c' → 2 (even) The maximum odd frequency is 3 (for 'a') and the maximum even fr...
Read more

Top 10 Beginner-Friendly LeetCode Questions and Their Solutions

If you're new to solving coding problems on LeetCode, it can feel overwhelming. Where do you start? Which problems are suitable for beginners? Don’t worry! In this blog post, I’ll guide you through   10 beginner-friendly LeetCode questions   that are perfect for getting started on your coding journey. These problems will help you build confidence, improve your problem-solving skills, and lay a solid foundation in data structures and algorithms. Why Start with Beginner-Friendly Problems? Before diving into advanced topics like dynamic programming or graph theory, it’s essential to: Build a strong foundation in basic programming concepts. Understand how to approach a coding problem methodically. Gain familiarity with LeetCode’s platform and its problem structure. The following problems are simple yet impactful, designed to introduce you to common techniques like loops, arrays, strings, and basic math operations. 10 Beginner-Friendly LeetCode Problems 1.  Two Sum (Easy) Prob...
Read more

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....
Read more