Simple Java Solution | No HashMap | Deque Approach
IntuitionThe problem talks about tracking user mentions in a chat system with various event types and user statuses. The initial thoughts would be to process ev
# Intuition
The problem talks about tracking user mentions in a chat system with various event types and user statuses. The initial thoughts would be to process events chronologically, keeping track of online/offline users and updating mention counts based on different message types.

# Approach
1. Sort events by timestamp, prioritizing **OFFLINE** events over **MESSAGE** events when timestamps are equal.
2. Process events sequentially:
   - For offline events: Mark users as offline and schedule their return.
   - For message events: Update mentions based on the message type (**ALL**, **HERE**, or specific users).
3. Maintain a queue of offline users to efficiently track when they come back online.
4. Use arrays to keep track of online status and mention counts for each user.

# Complexity
- Time complexity: $$O(n \log n)$$
  - Sorting events takes $$O(n \log n)$$ where n is the number of events.
  - Processing each event is $$O(1)$$ on average, but can be O(m) for messages mentioning specific users, where m is the number of mentioned users.
  - Overall, the sorting dominates, so it's $$O(n log n)$$.

- Space complexity: $$O(n)$$
  - We use arrays of size numberOfUsers for tracking online status and mentions: $$O(numberOfUsers)$$
  - The offlineUsers queue can potentially store all users: $$O(numberOfUsers)$$
  - The sorting algorithm may use additional space: O(n) for n events
  - Overall, it's $$O(n + numberOfUsers)$$, which simplifies to $$O(n)$$ as n ≥ numberOfUsers.

# Code
```java []
class Solution {

    private static final String MESSAGE_EVENT_TYPE = "MESSAGE";

    private static final String ALL_TOKEN = "ALL";

    private static final String HERE_TOKEN = "HERE";

    public int[] countMentions(int numberOfUsers, List<List<String>> events) {

        Deque<int[]> offlineUsers = new ArrayDeque<>();
        boolean[] onlineUsers = new boolean[numberOfUsers];

        int[] mentions = new int[numberOfUsers];

        Arrays.fill(onlineUsers, true);

        sortEvents(events);

        for (List<String> event : events) {
            processEvent(event, mentions, onlineUsers, offlineUsers);
        }

        return mentions;

    }

    void sortEvents(List<List<String>> events) {

        events.sort((event1, event2) -> {

            String event1Type = event1.get(0);
            String event2Type = event2.get(0);

            int timeStamp1 = Integer.parseInt(event1.get(1));
            int timeStamp2 = Integer.parseInt(event2.get(1));

            if (timeStamp1 == timeStamp2) {

                if (event1Type.equals(event2Type)) {
                    return 0;
                }

                return event1Type.equals(MESSAGE_EVENT_TYPE) ? 1 : -1;
            }

            return timeStamp1 - timeStamp2;
        });
    }

    void processEvent(List<String> event, int[] mentions, boolean[] onlineUsers, Deque<int[]> offlineUsers) {

        String eventType = event.get(0);

        int timeStamp = Integer.parseInt(event.get(1));

        String[] users = event.get(2).split(" ");

        String token = users[0];

        if (eventType.equals(MESSAGE_EVENT_TYPE)) {

            if (token.equals(ALL_TOKEN)) {

                updateMentionsForAllUsers(mentions);

            }
            else if (token.equals(HERE_TOKEN)) {

                updateOnlineUsers(onlineUsers, offlineUsers, timeStamp);

                updateMentionsForUsers(mentions, onlineUsers);

            }
            else {
                updateMentionsForUsers(mentions, users);
            }
        }
        else {

            updateOnlineUsers(onlineUsers, offlineUsers, timeStamp);

            updateOfflineUsers(offlineUsers, onlineUsers, timeStamp, users[0]);
        }
    }

    void updateMentionsForAllUsers(int[] mentions) {

        for (int i = 0; i < mentions.length; i++) {
            mentions[i]++;
        }
    }

    void updateMentionsForUsers(int[] mentions, String[] users) {

        for (String user : users) {
            int userId = Integer.parseInt(user.substring(2));
            mentions[userId]++;
        }
    }

    void updateMentionsForUsers(int[] mentions, boolean[] onlineUsers) {
        for (int i = 0; i < onlineUsers.length; i++) {
            if (onlineUsers[i]) {
                mentions[i]++;
            }
        }
    }

    void updateOnlineUsers(boolean[] onlineUsers, Deque<int[]> offlineUsers, int timeStamp) {

        while (!offlineUsers.isEmpty() && offlineUsers.peekFirst()[1] <= timeStamp) {
            onlineUsers[offlineUsers.peekFirst()[0]] = true;
            offlineUsers.removeFirst();
        }
    }

    void updateOfflineUsers(Deque<int[]> offlineUsers, boolean[] onlineUsers, int timeStamp, String user) {
        int userId = Integer.parseInt(user);
        offlineUsers.addLast(new int[] {
            userId,
            timeStamp + 60
        });
        onlineUsers[userId] = false;
    }
}

```
['Java']