Count Mentions Per User

Problem

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", "timestampi", "mentions_stringi"]
- This event indicates that a set of users was mentioned in a message at timestampi.
- The mentions_stringi 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", "timestampi", "idi"]
- This event indicates that the user idi had become offline at timestampi for 60 time units. The user will automatically be online again at time timestampi + 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.

Example 1

1
2
3
4
5
6
7
8
9


Input: numberOfUsers = 2, events = [["MESSAGE","10","id1
id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]
Output: [2,2]
Explanation:
Initially, all users are online.
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 `"HERE"` is mentioned.
`mentions = [2,2]`

Example 2

1
2
3
4
5
6
7
8
9


Input: numberOfUsers = 2, events = [["MESSAGE","10","id1
id0"],["OFFLINE","11","0"],["MESSAGE","12","ALL"]]
Output: [2,2]
Explanation:
Initially, all users are online.
At timestamp 10, `id1` and `id0` are mentioned. `mentions = [1,1]`
At timestamp 11, `id0` goes **offline.**
At timestamp 12, `"ALL"` is mentioned. This includes offline users, so both
`id0` and `id1` are mentioned. `mentions = [2,2]`

Example 3

1
2
3
4
5
6
7
8


Input: numberOfUsers = 2, events =
[["OFFLINE","10","0"],["MESSAGE","12","HERE"]]
Output: [0,1]
Explanation:
Initially, all users are online.
At timestamp 10, `id0` goes **offline.**
At timestamp 12, `"HERE"` is mentioned. Because `id0` is still offline, they
will not be mentioned. `mentions = [0,1]`

Constraints

1 <= numberOfUsers <= 100
1 <= events.length <= 100
events[i].length == 3
events[i][0] will be one of MESSAGE or OFFLINE.
1 <= int(events[i][1]) <= 10^5
The number of id<number> mentions in any "MESSAGE" event is between 1 and 100.
0 <= <number> <= numberOfUsers - 1
It is guaranteed that the user id referenced in the OFFLINE event is online at the time the event occurs.

Examples

Solution

Method 1 – Simulation with Event Processing

Intuition

Simulate the events in order, keeping track of each user’s online status and when they will come back online. For each message, count mentions according to the rules for id<number>, ALL, and HERE.

Approach

Sort all events by timestamp. For events with the same timestamp, process OFFLINE before MESSAGE.
Track for each user:
- Whether they are online.
- When they will come back online (if offline).
For each event:
- If OFFLINE: mark user as offline and set their online-again time.
- Before each event, check if any user should come back online at this timestamp.
- If MESSAGE:
  - If mentions string contains ALL, add 1 mention for every user.
  - If mentions string contains HERE, add 1 mention for every online user.
  - Otherwise, parse all id<number> tokens and add 1 mention for each occurrence (including duplicates, even if user is offline).
Return the mentions array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution {
public:
    vector<int> countMentionsPerUser(int numberOfUsers, vector<vector<string>>& events) {
        vector<tuple<int, int, int, string>> evs;
        for (auto& e : events) {
            int t = stoi(e[1]);
            if (e[0] == "OFFLINE") evs.push_back({t, 0, stoi(e[2]), ""});
            else evs.push_back({t, 1, -1, e[2]});
        }
        sort(evs.begin(), evs.end());
        vector<int> mentions(numberOfUsers);
        vector<bool> online(numberOfUsers, true);
        vector<int> back(numberOfUsers, -1);
        for (int i = 0; i < evs.size(); ++i) {
            int t, typ, id; string s;
            tie(t, typ, id, s) = evs[i];
            for (int u = 0; u < numberOfUsers; ++u) if (!online[u] && back[u] == t) online[u] = true;
            if (typ == 0) { // OFFLINE
                online[id] = false;
                back[id] = t + 60;
            } else { // MESSAGE
                if (s.find("ALL") != string::npos) {
                    for (int u = 0; u < numberOfUsers; ++u) mentions[u]++;
                } else if (s.find("HERE") != string::npos) {
                    for (int u = 0; u < numberOfUsers; ++u) if (online[u]) mentions[u]++;
                } else {
                    istringstream iss(s);
                    string tok;
                    while (iss >> tok) {
                        if (tok.substr(0, 2) == "id") {
                            int u = stoi(tok.substr(2));
                            mentions[u]++;
                        }
                    }
                }
            }
        }
        return mentions;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


func countMentionsPerUser(numberOfUsers int, events [][]string) []int {
    type event struct{t, typ, id int; s string}
    evs := []event{}
    for _, e := range events {
        t := atoi(e[1])
        if e[0] == "OFFLINE" {
            evs = append(evs, event{t, 0, atoi(e[2]), ""})
        } else {
            evs = append(evs, event{t, 1, -1, e[2]})
        }
    }
    sort.Slice(evs, func(i, j int) bool {
        if evs[i].t != evs[j].t { return evs[i].t < evs[j].t }
        return evs[i].typ < evs[j].typ
    })
    mentions := make([]int, numberOfUsers)
    online := make([]bool, numberOfUsers)
    for i := range online { online[i] = true }
    back := make([]int, numberOfUsers)
    for i := range back { back[i] = -1 }
    for _, ev := range evs {
        for u := 0; u < numberOfUsers; u++ {
            if !online[u] && back[u] == ev.t { online[u] = true }
        }
        if ev.typ == 0 {
            online[ev.id] = false
            back[ev.id] = ev.t + 60
        } else {
            if strings.Contains(ev.s, "ALL") {
                for u := 0; u < numberOfUsers; u++ { mentions[u]++ }
            } else if strings.Contains(ev.s, "HERE") {
                for u := 0; u < numberOfUsers; u++ { if online[u] { mentions[u]++ } }
            } else {
                for _, tok := range strings.Fields(ev.s) {
                    if strings.HasPrefix(tok, "id") {
                        u, _ := strconv.Atoi(tok[2:])
                        mentions[u]++
                    }
                }
            }
        }
    }
    return mentions
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class Solution {
    public int[] countMentionsPerUser(int numberOfUsers, String[][] events) {
        List<Event> evs = new ArrayList<>();
        for (String[] e : events) {
            int t = Integer.parseInt(e[1]);
            if (e[0].equals("OFFLINE")) evs.add(new Event(t, 0, Integer.parseInt(e[2]), ""));
            else evs.add(new Event(t, 1, -1, e[2]));
        }
        Collections.sort(evs);
        int[] mentions = new int[numberOfUsers];
        boolean[] online = new boolean[numberOfUsers];
        Arrays.fill(online, true);
        int[] back = new int[numberOfUsers];
        Arrays.fill(back, -1);
        for (Event ev : evs) {
            for (int u = 0; u < numberOfUsers; ++u) if (!online[u] && back[u] == ev.t) online[u] = true;
            if (ev.typ == 0) {
                online[ev.id] = false;
                back[ev.id] = ev.t + 60;
            } else {
                if (ev.s.contains("ALL")) {
                    for (int u = 0; u < numberOfUsers; ++u) mentions[u]++;
                } else if (ev.s.contains("HERE")) {
                    for (int u = 0; u < numberOfUsers; ++u) if (online[u]) mentions[u]++;
                } else {
                    for (String tok : ev.s.split(" ")) {
                        if (tok.startsWith("id")) {
                            int u = Integer.parseInt(tok.substring(2));
                            mentions[u]++;
                        }
                    }
                }
            }
        }
        return mentions;
    }
    static class Event implements Comparable<Event> {
        int t, typ, id; String s;
        Event(int t, int typ, int id, String s) { this.t = t; this.typ = typ; this.id = id; this.s = s; }
        public int compareTo(Event o) {
            if (t != o.t) return t - o.t;
            return typ - o.typ;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    fun countMentionsPerUser(numberOfUsers: Int, events: Array<Array<String>>): IntArray {
        data class Event(val t: Int, val typ: Int, val id: Int, val s: String): Comparable<Event> {
            override fun compareTo(other: Event): Int = if (t != other.t) t - other.t else typ - other.typ
        }
        val evs = events.map {
            val t = it[1].toInt()
            if (it[0] == "OFFLINE") Event(t, 0, it[2].toInt(), "") else Event(t, 1, -1, it[2])
        }.sorted()
        val mentions = IntArray(numberOfUsers)
        val online = BooleanArray(numberOfUsers) { true }
        val back = IntArray(numberOfUsers) { -1 }
        for (ev in evs) {
            for (u in 0 until numberOfUsers) if (!online[u] && back[u] == ev.t) online[u] = true
            if (ev.typ == 0) {
                online[ev.id] = false
                back[ev.id] = ev.t + 60
            } else {
                if (ev.s.contains("ALL")) {
                    for (u in 0 until numberOfUsers) mentions[u]++
                } else if (ev.s.contains("HERE")) {
                    for (u in 0 until numberOfUsers) if (online[u]) mentions[u]++
                } else {
                    for (tok in ev.s.split(" ")) {
                        if (tok.startsWith("id")) {
                            val u = tok.substring(2).toInt()
                            mentions[u]++
                        }
                    }
                }
            }
        }
        return mentions
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution:
    def countMentionsPerUser(self, numberOfUsers: int, events: list[list[str]]) -> list[int]:
        evs = []
        for e in events:
            t = int(e[1])
            if e[0] == "OFFLINE":
                evs.append((t, 0, int(e[2]), ""))
            else:
                evs.append((t, 1, -1, e[2]))
        evs.sort()
        mentions = [0] * numberOfUsers
        online = [True] * numberOfUsers
        back = [-1] * numberOfUsers
        for t, typ, idx, s in evs:
            for u in range(numberOfUsers):
                if not online[u] and back[u] == t:
                    online[u] = True
            if typ == 0:
                online[idx] = False
                back[idx] = t + 60
            else:
                if "ALL" in s:
                    for u in range(numberOfUsers):
                        mentions[u] += 1
                elif "HERE" in s:
                    for u in range(numberOfUsers):
                        if online[u]:
                            mentions[u] += 1
                else:
                    for tok in s.split():
                        if tok.startswith("id"):
                            u = int(tok[2:])
                            mentions[u] += 1
        return mentions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


impl Solution {
    pub fn count_mentions_per_user(number_of_users: i32, events: Vec<Vec<String>>) -> Vec<i32> {
        let n = number_of_users as usize;
        let mut evs = vec![];
        for e in events.iter() {
            let t = e[1].parse::<i32>().unwrap();
            if e[0] == "OFFLINE" {
                evs.push((t, 0, e[2].parse::<usize>().unwrap(), String::new()));
            } else {
                evs.push((t, 1, usize::MAX, e[2].clone()));
            }
        }
        evs.sort();
        let mut mentions = vec![0; n];
        let mut online = vec![true; n];
        let mut back = vec![-1; n];
        for (t, typ, idx, s) in evs {
            for u in 0..n {
                if !online[u] && back[u] == t {
                    online[u] = true;
                }
            }
            if typ == 0 {
                online[idx] = false;
                back[idx] = t + 60;
            } else {
                if s.contains("ALL") {
                    for u in 0..n { mentions[u] += 1; }
                } else if s.contains("HERE") {
                    for u in 0..n { if online[u] { mentions[u] += 1; } }
                } else {
                    for tok in s.split_whitespace() {
                        if tok.starts_with("id") {
                            let u = tok[2..].parse::<usize>().unwrap();
                            mentions[u] += 1;
                        }
                    }
                }
            }
        }
        mentions.into_iter().map(|x| x as i32).collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    countMentionsPerUser(numberOfUsers: number, events: string[][]): number[] {
        type Event = { t: number, typ: number, id: number, s: string };
        const evs: Event[] = [];
        for (const e of events) {
            const t = +e[1];
            if (e[0] === "OFFLINE") evs.push({ t, typ: 0, id: +e[2], s: "" });
            else evs.push({ t, typ: 1, id: -1, s: e[2] });
        }
        evs.sort((a, b) => a.t - b.t || a.typ - b.typ);
        const mentions = Array(numberOfUsers).fill(0);
        const online = Array(numberOfUsers).fill(true);
        const back = Array(numberOfUsers).fill(-1);
        for (const ev of evs) {
            for (let u = 0; u < numberOfUsers; ++u) if (!online[u] && back[u] === ev.t) online[u] = true;
            if (ev.typ === 0) {
                online[ev.id] = false;
                back[ev.id] = ev.t + 60;
            } else {
                if (ev.s.includes("ALL")) {
                    for (let u = 0; u < numberOfUsers; ++u) mentions[u]++;
                } else if (ev.s.includes("HERE")) {
                    for (let u = 0; u < numberOfUsers; ++u) if (online[u]) mentions[u]++;
                } else {
                    for (const tok of ev.s.split(/\s+/)) {
                        if (tok.startsWith("id")) {
                            const u = +tok.slice(2);
                            mentions[u]++;
                        }
                    }
                }
            }
        }
        return mentions;
    }
}

Complexity

⏰ Time complexity: O(n * m) where n is the number of events and m is the number of users (since for each event we may scan all users).
🧺 Space complexity: O(m) for user status and mentions arrays.

Problem#

Example 1#

Example 2#

Example 3#

Constraints#

Examples#

Solution#

Method 1 – Simulation with Event Processing#

Intuition#

Approach#

Code#

Complexity#