Finding the Users Active Minutes — Problem & Solution
Finding the Users Active Minutes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Finding the Users Active Minutes is a medium coding problem on arrays and hash table, asked in Twitter interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the activity logs of a site, where logs[i] = [ID, time] records that the user with ID took an action at minute time. Several users may act in the same minute, and one user may act several times in the same minute.
A user's active minutes (UAM) is the number of distinct minutes in which that user took at least one action.
Return an array answer of length k (1-indexed by UAM) where answer[j - 1] is the number of users whose UAM equals j. It is guaranteed that every user's UAM is at most k.
Example 1
Input: logs = [[3,10],[3,10],[7,1],[3,11],[7,1]], k = 3
Output: [1,1,0]
Explanation: User 3 acted in minutes 10 and 11 (UAM 2); the repeat in minute 10 counts once. User 7 acted only in minute 1 (UAM 1).
Example 2
Input: logs = [[1,1],[2,2],[2,3]], k = 4
Output: [1,1,0,0]
Explanation: User 1 has UAM 1 and user 2 has UAM 2; no user reaches 3 or 4.
Example 3
Input: logs = [[5,4]], k = 1
Output: [1]
Constraints
1 <= logs.length <= 10^40 <= ID <= 10^91 <= time <= 10^5k is in the range [the maximum UAM of any user, 10^5]
Hints for Finding the Users Active Minutes
Hint 1
A user's UAM is the size of the set of minutes they appear with.
Hint 2
Map each user ID to a set of minutes in one pass over the logs.
Hint 3
Then bucket the users by the size of their set into an array of length
k.
How to solve Finding the Users Active Minutes
Group the logs by user and deduplicate the minutes with a set: the set's size is the UAM. A final pass histograms those sizes.
Approach
- Build a map
ID → set of minutesfrom the logs. - Create
answerof lengthkfilled with zeros. - For each user, increment
answer[size - 1].
Why it works
The set keeps exactly the distinct minutes of each user, so its size is the UAM by definition, and every user is counted in exactly one bucket.
Complexity
- Time —
O(L) - Space —
O(L)
Pitfalls
- Repeated actions in the same minute must not inflate the UAM — count distinct minutes.
- The answer is indexed from UAM 1, so a user with UAM
jgoes to indexj - 1. - IDs reach 10^9: key a map by them rather than indexing an array.
Reference solution
Python
from typing import List
def findingUsersActiveMinutes(logs: List[List[int]], k: int) -> List[int]:
mins = {}
for uid, t in logs:
mins.setdefault(uid, set()).add(t)
ans = [0] * k
for s in mins.values():
ans[len(s) - 1] += 1
return ansJava
public static int[] findingUsersActiveMinutes(int[][] logs, int k) {
Map<Integer, Set<Integer>> mins = new HashMap<>();
for (int[] log : logs) mins.computeIfAbsent(log[0], x -> new HashSet<>()).add(log[1]);
int[] ans = new int[k];
for (Set<Integer> s : mins.values()) ans[s.size() - 1]++;
return ans;
}C++
vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
unordered_map<int, unordered_set<int>> mins;
for (auto& log : logs) mins[log[0]].insert(log[1]);
vector<int> ans(k, 0);
for (auto& e : mins) ans[e.second.size() - 1]++;
return ans;
}JavaScript
var findingUsersActiveMinutes = function(logs, k) {
var mins = new Map();
for (var i = 0; i < logs.length; i++) {
var id = logs[i][0];
if (!mins.has(id)) mins.set(id, new Set());
mins.get(id).add(logs[i][1]);
}
var ans = new Array(k).fill(0);
mins.forEach(function(s) { ans[s.size - 1]++; });
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets