Problem Description
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] = [ID_i, time_i] indicates that the user with ID_i performed an action at the minute time_i. 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.
Key Insights
- Each user can perform multiple actions in the same minute, but only unique minutes count towards their UAM.
- We need to track the UAM for each user, which can be efficiently done using a set.
- The final result requires counting how many users have a specific UAM and storing this in an array of size k.
Space and Time Complexity
Time Complexity: O(n) where n is the number of logs, as we need to traverse each log to compute unique minutes for each user.
Space Complexity: O(u + k) where u is the number of unique users, and k is the size of the output array. We use a set to store unique minutes for each user.
Solution
To solve the problem, we can use a hash table (dictionary) to map each user ID to a set of unique minutes in which they performed actions. We will iterate through the logs, updating the sets for each user. After determining the UAM for each user, we will create an answer array where the index corresponds to the UAM and the value at that index corresponds to the number of users with that UAM.