How do you solve Count Mentions Per User on LeetCode?

Count Mentions Per User (LeetCode #3433) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Sorting events by timestamp is crucial for processing in the correct order.

What is the time complexity of Count Mentions Per User?

The optimal solution for Count Mentions Per User runs in O(n log n) time and uses O(n) space. The time complexity is O(n log n) due to sorting the events. The space complexity is O(n) for storing the mentions and offline users.

What is the brute force solution for Count Mentions Per User?

The brute force approach for Count Mentions Per User is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will process each message event and check against all users to see if they are mentioned. This is straightforward but inefficient, especially with many users and events. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Count Mentions Per User?

Count Mentions Per User uses the following concepts: Array, Math, Sorting, Simulation. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Count Mentions Per User?

Clarify the problem requirements and edge cases upfront. Discuss your thought process while coding to demonstrate understanding. Test your solution with sample inputs to ensure correctness.

What are common mistakes when solving Count Mentions Per User?

Not updating the online/offline status before processing messages. Confusing the logic for ALL and HERE mentions.

#3433

Count Mentions Per User

Medium

ArrayMathSortingSimulationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

This approach efficiently manages user states and counts mentions by leveraging sorting and sets to track online/offline status, allowing us to process each event in a single pass.

⚙️

Algorithm

5 steps

1Step 1: Sort events by timestamp.
2Step 2: Initialize a mentions array of size numberOfUsers to zero.
3Step 3: Use a set to track offline users and a variable to track when users come back online.
4Step 4: For each event, update the online/offline status of users before processing message mentions.
5Step 5: For MESSAGE events, increment the mentions count based on the current online users.

solution.py33 lines

1def count_mentions(numberOfUsers, events):
2    events.sort(key=lambda x: int(x[1]))
3    mentions = [0] * numberOfUsers
4    offline_users = set()
5    online_until = [0] * numberOfUsers
6    for event in events:
7        event_type, timestamp = event[0], int(event[1])
8        # Update user status before processing the event
9        for i in range(numberOfUsers):
10            if online_until[i] > timestamp:
11                offline_users.discard(i)
12            else:
13                offline_users.add(i)
14        if event_type == 'MESSAGE':
15            mentions_string = event[2].split()
16            for mention in mentions_string:
17                if mention == 'ALL':
18                    for i in range(numberOfUsers):
19                        if i not in offline_users:
20                            mentions[i] += 1
21                elif mention == 'HERE':
22                    for i in range(numberOfUsers):
23                        if i not in offline_users:
24                            mentions[i] += 1
25                else:
26                    user_id = int(mention[2:])
27                    if user_id not in offline_users:
28                        mentions[user_id] += 1
29        elif event_type == 'OFFLINE':
30            user_id = int(event[2])
31            offline_users.add(user_id)
32            online_until[user_id] = timestamp + 60
33    return mentions

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the events. The space complexity is O(n) for storing the mentions and offline users.

1Sorting events by timestamp is crucial for processing in the correct order.
2Using sets to track online/offline users allows efficient status checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.