LeetCode #3433 — MEDIUM

Count Mentions Per User

Move from brute-force thinking to an efficient approach using array strategy.

The Problem

Problem Statement

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", "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.

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]) <= 10⁵
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.

Step 01

Brute Force Baseline

Problem summary: 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]

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Math

Example 1

2
[["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]

Example 2

2
[["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","12","ALL"]]

Example 3

2
[["OFFLINE","10","0"],["MESSAGE","12","HERE"]]

Step 02

Core Insight

What unlocks the optimal approach

Sort events by timestamp and then process each event.
Maintain two sets for offline and online user IDs.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3433: Count Mentions Per User
class Solution {
    public int[] countMentions(int numberOfUsers, List<List<String>> events) {
        events.sort((a, b) -> {
            int x = Integer.parseInt(a.get(1));
            int y = Integer.parseInt(b.get(1));
            if (x == y) {
                return a.get(0).charAt(2) - b.get(0).charAt(2);
            }
            return x - y;
        });
        int[] ans = new int[numberOfUsers];
        int[] onlineT = new int[numberOfUsers];
        int lazy = 0;
        for (var e : events) {
            String etype = e.get(0);
            int cur = Integer.parseInt(e.get(1));
            String s = e.get(2);
            if (etype.charAt(0) == 'O') {
                onlineT[Integer.parseInt(s)] = cur + 60;
            } else if (s.charAt(0) == 'A') {
                ++lazy;
            } else if (s.charAt(0) == 'H') {
                for (int i = 0; i < numberOfUsers; ++i) {
                    if (onlineT[i] <= cur) {
                        ++ans[i];
                    }
                }
            } else {
                for (var a : s.split(" ")) {
                    ++ans[Integer.parseInt(a.substring(2))];
                }
            }
        }
        if (lazy > 0) {
            for (int i = 0; i < numberOfUsers; ++i) {
                ans[i] += lazy;
            }
        }
        return ans;
    }
}

// Accepted solution for LeetCode #3433: Count Mentions Per User
func countMentions(numberOfUsers int, events [][]string) []int {
	sort.Slice(events, func(i, j int) bool {
		x, _ := strconv.Atoi(events[i][1])
		y, _ := strconv.Atoi(events[j][1])
		if x == y {
			return events[i][0][2] < events[j][0][2]
		}
		return x < y
	})

	ans := make([]int, numberOfUsers)
	onlineT := make([]int, numberOfUsers)
	lazy := 0

	for _, e := range events {
		etype := e[0]
		cur, _ := strconv.Atoi(e[1])
		s := e[2]

		if etype[0] == 'O' {
			userID, _ := strconv.Atoi(s)
			onlineT[userID] = cur + 60
		} else if s[0] == 'A' {
			lazy++
		} else if s[0] == 'H' {
			for i := 0; i < numberOfUsers; i++ {
				if onlineT[i] <= cur {
					ans[i]++
				}
			}
		} else {
			mentions := strings.Split(s, " ")
			for _, m := range mentions {
				userID, _ := strconv.Atoi(m[2:])
				ans[userID]++
			}
		}
	}

	if lazy > 0 {
		for i := 0; i < numberOfUsers; i++ {
			ans[i] += lazy
		}
	}

	return ans
}

# Accepted solution for LeetCode #3433: Count Mentions Per User
class Solution:
    def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
        events.sort(key=lambda e: (int(e[1]), e[0][2]))
        ans = [0] * numberOfUsers
        online_t = [0] * numberOfUsers
        lazy = 0
        for etype, ts, s in events:
            cur = int(ts)
            if etype[0] == "O":
                online_t[int(s)] = cur + 60
            elif s[0] == "A":
                lazy += 1
            elif s[0] == "H":
                for i, t in enumerate(online_t):
                    if t <= cur:
                        ans[i] += 1
            else:
                for a in s.split():
                    ans[int(a[2:])] += 1
        if lazy:
            for i in range(numberOfUsers):
                ans[i] += lazy
        return ans

// Accepted solution for LeetCode #3433: Count Mentions Per User
impl Solution {
    pub fn count_mentions(number_of_users: i32, mut events: Vec<Vec<String>>) -> Vec<i32> {
        let n = number_of_users as usize;

        events.sort_by(|a, b| {
            let x: i32 = a[1].parse().unwrap();
            let y: i32 = b[1].parse().unwrap();
            if x == y {
                a[0].as_bytes()[2].cmp(&b[0].as_bytes()[2])
            } else {
                x.cmp(&y)
            }
        });

        let mut ans = vec![0_i32; n];
        let mut online_t = vec![0_i32; n];
        let mut lazy = 0_i32;

        for e in events {
            let etype = &e[0];
            let cur: i32 = e[1].parse().unwrap();
            let s = &e[2];

            let c0 = etype.as_bytes()[0] as char;

            if c0 == 'O' {
                let uid: usize = s.parse().unwrap();
                online_t[uid] = cur + 60;

            } else if s.as_bytes()[0] as char == 'A' {
                lazy += 1;

            } else if s.as_bytes()[0] as char == 'H' {
                for i in 0..n {
                    if online_t[i] <= cur {
                        ans[i] += 1;
                    }
                }

            } else {
                for a in s.split(' ') {
                    let uid: usize = a[2..].parse().unwrap();
                    ans[uid] += 1;
                }
            }
        }

        if lazy > 0 {
            for i in 0..n {
                ans[i] += lazy;
            }
        }

        ans
    }
}

// Accepted solution for LeetCode #3433: Count Mentions Per User
function countMentions(numberOfUsers: number, events: string[][]): number[] {
    events.sort((a, b) => {
        const x = +a[1];
        const y = +b[1];
        if (x === y) {
            return a[0].charAt(2) < b[0].charAt(2) ? -1 : 1;
        }
        return x - y;
    });

    const ans: number[] = Array(numberOfUsers).fill(0);
    const onlineT: number[] = Array(numberOfUsers).fill(0);
    let lazy = 0;

    for (const [etype, ts, s] of events) {
        const cur = +ts;
        if (etype.charAt(0) === 'O') {
            const userID = +s;
            onlineT[userID] = cur + 60;
        } else if (s.charAt(0) === 'A') {
            lazy++;
        } else if (s.charAt(0) === 'H') {
            for (let i = 0; i < numberOfUsers; i++) {
                if (onlineT[i] <= cur) {
                    ans[i]++;
                }
            }
        } else {
            const mentions = s.split(' ');
            for (const m of mentions) {
                const userID = +m.slice(2);
                ans[userID]++;
            }
        }
    }

    if (lazy > 0) {
        for (let i = 0; i < numberOfUsers; i++) {
            ans[i] += lazy;
        }
    }

    return ans;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n + m × log m log M + L)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.