Finding the Users Active Minutes

Medium
1789.

Finding the Users Active Minutes

Finding the Users Active Minutes is a medium coding problem on arrays and hash table, asked in Twitter interviews.

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^4
  • 0 <= ID <= 10^9
  • 1 <= time <= 10^5
  • k is in the range [the maximum UAM of any user, 10^5]
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} logs
 * @param {number} k
 * @return {number[]}
 */
var findingUsersActiveMinutes = function(logs, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 0 <= ID <= 10^9
  • 1 <= time <= 10^5
  • k is in the range [the maximum UAM of any user, 10^5]

Hints for Finding the Users Active Minutes

  1. Hint 1

    A user's UAM is the size of the set of minutes they appear with.

  2. Hint 2

    Map each user ID to a set of minutes in one pass over the logs.

  3. 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

  1. Build a map ID → set of minutes from the logs.
  2. Create answer of length k filled with zeros.
  3. 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 j goes to index j - 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 ans

Java

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