Count Mentions Per User
Source: leetcode
Difficulty: Medium
Tags: array, math, sorting, simulation

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:


1. **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.
2. **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:**



**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:**



**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:**



**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]) <= 105`
- 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.




C++ solution:
class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        vector<tuple<int, int, int, vector<string>>> sorted_events;
        for (int i = 0; i < events.size(); ++i) {
            int timestamp = stoi(events[i][1]);
            int type = (events[i][0] == "OFFLINE") ? 0 : 1;
            sorted_events.emplace_back(timestamp, type, i, events[i]);
        }
        sort(sorted_events.begin(), sorted_events.end());
        
        vector<int> online_time(numberOfUsers, 0);
        vector<int> mentions(numberOfUsers, 0);
        
        for (auto& t : sorted_events) {
            auto& e = get<3>(t);
            if (e[0] == "OFFLINE") {
                int event_time = get<0>(t);
                int user_id = stoi(e[2]);
                online_time[user_id] = event_time + 60;
            } else {
                int event_time = get<0>(t);
                string mentions_str = e[2];
                vector<string> tokens = split(mentions_str, ' ');
                for (string& token : tokens) {
                    if (token == "ALL") {
                        for (int i = 0; i < numberOfUsers; ++i) {
                            mentions[i]++;
                        }
                    } else if (token == "HERE") {
                        for (int i = 0; i < numberOfUsers; ++i) {
                            if (event_time >= online_time[i]) {
                                mentions[i]++;
                            }
                        }
                    } else if (token.substr(0, 2) == "id") {
                        int user_id = stoi(token.substr(2));
                        mentions[user_id]++;
                    }
                }
            }
        }
        
        return mentions;
    }

private:
    vector<string> split(const string& s, char delimiter) {
        vector<string> tokens;
        string token;
        istringstream tokenStream(s);
        while (getline(tokenStream, token, delimiter)) {
            if (!token.empty()) {
                tokens.push_back(token);
            }
        }
        return tokens;
    }
};

Go solution:
func countMentions(numberOfUsers int, events [][]string) []int {
    type eventInfo struct {
        originalIndex int
        timestamp     int
        eventType     int // 0: OFFLINE, 1: MESSAGE
        data          []string
    }

    eventList := make([]eventInfo, len(events))
    for i, e := range events {
        ts, _ := strconv.Atoi(e[1])
        typ := 0
        if e[0] == "MESSAGE" {
            typ = 1
        }
        eventList[i] = eventInfo{
            originalIndex: i,
            timestamp:     ts,
            eventType:     typ,
            data:          e,
        }
    }

    sort.SliceStable(eventList, func(i, j int) bool {
        a, b := eventList[i], eventList[j]
        if a.timestamp != b.timestamp {
            return a.timestamp < b.timestamp
        }
        if a.eventType != b.eventType {
            return a.eventType < b.eventType
        }
        return a.originalIndex < b.originalIndex
    })

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

    for _, ei := range eventList {
        e := ei.data
        if e[0] == "OFFLINE" {
            ts, _ := strconv.Atoi(e[1])
            userID, _ := strconv.Atoi(e[2])
            newEnd := ts + 60
            if newEnd > offlineEnd[userID] {
                offlineEnd[userID] = newEnd
            }
        } else {
            ts, _ := strconv.Atoi(e[1])
            mentionsStr := e[2]
            tokens := strings.Split(mentionsStr, " ")
            for _, token := range tokens {
                switch token {
                case "ALL":
                    for i := 0; i < numberOfUsers; i++ {
                        mentions[i]++
                    }
                case "HERE":
                    for i := 0; i < numberOfUsers; i++ {
                        if offlineEnd[i] <= ts {
                            mentions[i]++
                        }
                    }
                default:
                    if strings.HasPrefix(token, "id") {
                        idStr := token[2:]
                        id, _ := strconv.Atoi(idStr)
                        if id >= 0 && id < numberOfUsers {
                            mentions[id]++
                        }
                    }
                }
            }
        }
    }

    return mentions
}

Java solution:
class Solution {
    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < events.size(); i++) {
            indices.add(i);
        }

        Collections.sort(indices, (a, b) -> {
            List<String> eventA = events.get(a);
            List<String> eventB = events.get(b);
            int tA = Integer.parseInt(eventA.get(1));
            int tB = Integer.parseInt(eventB.get(1));
            if (tA != tB) {
                return Integer.compare(tA, tB);
            } else {
                String typeA = eventA.get(0);
                String typeB = eventB.get(0);
                if (typeA.equals(typeB)) {
                    return Integer.compare(a, b);
                } else {
                    return typeA.equals("OFFLINE") ? -1 : 1;
                }
            }
        });

        int[] mentions = new int[numberOfUsers];
        int[] offlineUntil = new int[numberOfUsers];

        for (int i : indices) {
            List<String> event = events.get(i);
            String type = event.get(0);
            int timestamp = Integer.parseInt(event.get(1));
            if (type.equals("OFFLINE")) {
                int userId = Integer.parseInt(event.get(2));
                offlineUntil[userId] = timestamp + 60;
            } else {
                String mentionsString = event.get(2);
                String[] tokens = mentionsString.split(" ");
                for (String token : tokens) {
                    if (token.equals("ALL")) {
                        for (int j = 0; j < numberOfUsers; j++) {
                            mentions[j]++;
                        }
                    } else if (token.equals("HERE")) {
                        for (int j = 0; j < numberOfUsers; j++) {
                            if (timestamp >= offlineUntil[j]) {
                                mentions[j]++;
                            }
                        }
                    } else {
                        String idStr = token.substring(2);
                        int user = Integer.parseInt(idStr);
                        if (user >= 0 && user < numberOfUsers) {
                            mentions[user]++;
                        }
                    }
                }
            }
        }

        return mentions;
    }
}

JavaScript solution:
var countMentions = function(numberOfUsers, events) {
    events.sort((a, b) => {
        const timeA = parseInt(a[1]);
        const timeB = parseInt(b[1]);
        if (timeA !== timeB) {
            return timeA - timeB;
        } else {
            const typeA = a[0];
            const typeB = b[0];
            if (typeA === 'OFFLINE' && typeB === 'MESSAGE') return -1;
            if (typeA === 'MESSAGE' && typeB === 'OFFLINE') return 1;
            return 0;
        }
    });

    const mentions = new Array(numberOfUsers).fill(0);
    const offlineEndTimes = new Array(numberOfUsers).fill(0);

    for (const event of events) {
        const type = event[0];
        const timestamp = parseInt(event[1]);
        if (type === 'OFFLINE') {
            const userId = parseInt(event[2]);
            offlineEndTimes[userId] = timestamp + 60;
        } else {
            const tokens = event[2].split(' ');
            const users = [];
            for (const token of tokens) {
                if (token === 'ALL') {
                    for (let i = 0; i < numberOfUsers; i++) users.push(i);
                } else if (token === 'HERE') {
                    for (let i = 0; i < numberOfUsers; i++) {
                        if (offlineEndTimes[i] <= timestamp) users.push(i);
                    }
                } else {
                    const id = parseInt(token.substring(2));
                    users.push(id);
                }
            }
            users.forEach(id => mentions[id]++);
        }
    }

    return mentions;
};

Python solution:
class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        mentions = [0] * numberOfUsers
        offline_until = [0] * numberOfUsers
        
        sorted_events = sorted(events, key=lambda x: (int(x[1]), 0 if x[0] == 'OFFLINE' else 1))
        
        for event in sorted_events:
            event_type = event[0]
            timestamp = int(event[1])
            if event_type == 'OFFLINE':
                user_id = int(event[2])
                offline_until[user_id] = timestamp + 60
            else:
                mentions_str = event[2]
                tokens = mentions_str.split()
                for token in tokens:
                    if token == 'ALL':
                        for user in range(numberOfUsers):
                            mentions[user] += 1
                    elif token == 'HERE':
                        for user in range(numberOfUsers):
                            if offline_until[user] <= timestamp:
                                mentions[user] += 1
                    else:
                        user_id = int(token[2:])
                        mentions[user_id] += 1
        
        return mentions

Ruby solution:
def count_mentions(number_of_users, events)
  # Process events to include original index for stable sorting
  processed_events = events.each_with_index.map do |event, index|
    type, ts_str, data = event
    ts = ts_str.to_i
    type_priority = type == "OFFLINE" ? 0 : 1
    [ts, type_priority, index, event]
  end

  # Sort events by timestamp, then type (OFFLINE first), then original index
  sorted_events = processed_events.sort_by { |e| [e[0], e[1], e[2]] }

  # Initialize online_time and mentions arrays
  online_time = Array.new(number_of_users, 0)
  mentions = Array.new(number_of_users, 0)

  # Process each event in sorted order
  sorted_events.each do |e|
    original_event = e[3]
    type, ts_str, data = original_event
    ts = ts_str.to_i

    if type == "OFFLINE"
      # Update the user's online time
      user_id = data.to_i
      online_time[user_id] = ts + 60
    else
      # Process the message mentions
      mentions_str = data
      tokens = mentions_str.split(' ')
      mentioned_users = []

      tokens.each do |token|
        if token.start_with?('id')
          user_id = token[2..-1].to_i
          mentioned_users << user_id
        elsif token == 'ALL'
          mentioned_users += (0...number_of_users).to_a
        elsif token == 'HERE'
          online_users = (0...number_of_users).filter { |id| ts >= online_time[id] }
          mentioned_users += online_users
        end
      end

      # Update mentions count
      mentioned_users.each { |id| mentions[id] += 1 }
    end
  end

  mentions
end