Welcome to Subscribe On Youtube
1817. Finding the Users Active Minutes
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 1indexed 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.
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 <= 10^{4}
0 <= ID_{i} <= 10^{9}
1 <= time_{i} <= 10^{5}
k
is in the range[The maximum UAM for a user, 10^{5}]
.
Solutions
Solution 1: Hash Table
We use a hash table $d$ to record all the unique operation times of each user, and then traverse the hash table to count the number of active minutes for each user. Finally, we count the distribution of the number of active minutes for each user.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the $logs$ array.

class Solution { public int[] findingUsersActiveMinutes(int[][] logs, int k) { Map<Integer, Set<Integer>> d = new HashMap<>(); for (var log : logs) { int i = log[0], t = log[1]; d.computeIfAbsent(i, key > new HashSet<>()).add(t); } int[] ans = new int[k]; for (var ts : d.values()) { ++ans[ts.size()  1]; } return ans; } }

class Solution { public: vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) { unordered_map<int, unordered_set<int>> d; for (auto& log : logs) { int i = log[0], t = log[1]; d[i].insert(t); } vector<int> ans(k); for (auto& [_, ts] : d) { ++ans[ts.size()  1]; } return ans; } };

class Solution: def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) > List[int]: d = defaultdict(set) for i, t in logs: d[i].add(t) ans = [0] * k for ts in d.values(): ans[len(ts)  1] += 1 return ans

func findingUsersActiveMinutes(logs [][]int, k int) []int { d := map[int]map[int]bool{} for _, log := range logs { i, t := log[0], log[1] if _, ok := d[i]; !ok { d[i] = make(map[int]bool) } d[i][t] = true } ans := make([]int, k) for _, ts := range d { ans[len(ts)1]++ } return ans }

function findingUsersActiveMinutes(logs: number[][], k: number): number[] { const d: Map<number, Set<number>> = new Map(); for (const [i, t] of logs) { if (!d.has(i)) { d.set(i, new Set<number>()); } d.get(i)!.add(t); } const ans: number[] = Array(k).fill(0); for (const [_, ts] of d) { ++ans[ts.size  1]; } return ans; }