188.md

1817. Finding the Users Active Minutes

Difficulty: 🟡 Medium

You are given the logs for users' actions on LeetCode, and an integer k. The logs are represented by a 2D integer array logs where each logs[i] = [IDi, timei] indicates that the user with IDi performed an action at the minute timei.

Multiple users can perform actions simultaneously, and a single user can perform multiple actions in the same minute.

The user active minutes (UAM) for a given user is defined as the number of unique minutes in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.

You are to calculate a 1-indexed array answer of size k such that, for each j (1 <= j <= k), answer[j] is the number of users whose UAM equals j.

Return the array answer as described above.

Examples:

Example 1:

Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
Output: [0,2,0,0,0]
Explanation:
The user with ID=0 performed actions at minutes 5, 2, and 5 again. Hence, they have a UAM of 2 (minute 5 is only counted once).
The user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
Since both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.

Example 2:

Input: logs = [[1,1],[2,2],[2,3]], k = 4
Output: [1,1,0,0]
Explanation:
The user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1.
The user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
There is one user with a UAM of 1 and one with a UAM of 2.
Hence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.

Constraints:

• 1 <= logs.length <= 104
• 0 <= IDi <= 109
• 1 <= timei <= 105
• k is in the range [The maximum **UAM** for a user, 105].

Solutions

O(n) solution

Python3

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        UAM = defaultdict(set)
        for ID, time in logs:
            UAM[ID].add(time)

        unique_activity_to_users_count = defaultdict(int)
        for key in UAM:
            unique_activity_to_users_count[len(UAM[key])] += 1
        
        answer = [0] * k
        for j in range(k+1):
            answer[j-1] = unique_activity_to_users_count[j]

        return answer

The solution involves processing the logs to calculate the UAM for each user and then counting the number of users for each UAM value from 1 to k.

Here's a step-by-step explanation of the solution:

1. Initialize a dictionary UAM (User Active Minutes) as a defaultdict of sets. This dictionary will store the unique minutes of activity for each user.

2. Iterate through the logs. For each log entry [ID, time], add the time to the set of active minutes for the user with ID ID in the UAM dictionary.

3. Initialize a dictionary unique_activity_to_users_count as a defaultdict of integers. This dictionary will store the count of users for each unique activity (UAM).

4. Iterate through the keys in the UAM dictionary (which represent user IDs). For each user, calculate the length of their UAM set (i.e., the number of unique minutes of activity) and increment the corresponding count in the unique_activity_to_users_count dictionary.

5. Initialize an array answer of size k filled with zeros.

6. Iterate from j = 1 to k, and for each j, assign the count of users with UAM equal to j from the unique_activity_to_users_count dictionary to answer[j-1].

7. Return the answer array as the result.

Complexity Analysis

• Time Complexity: The solution iterates through each log entry to build the UAM dictionary, iterates through the keys in the UAM dictionary to build the unique_activity_to_users_count dictionary, and iterates from 1 to k to fill the answer array. The time complexity is O(N), where N is the number of log entries.

• Space Complexity: The space complexity is O(N) due to the UAM dictionary and the unique_activity_to_users_count dictionary.

Summary

The solution efficiently calculates the UAM for each user from the given logs and counts the number of users for each UAM value. It uses dictionaries to store and process the data, resulting in a time complexity of O(N), where N is the number of log entries.

NB: If you want to get community points please suggest solutions in other languages as merge requests.