Scale Engineer

Finding the Users Active Minutes

Med
#1661Time: O(N log N), where N is the number of logs. The sorting step dominates the complexity. The subsequent linear scan is O(N).Space: O(log N + k) or O(N + k). The space depends on the implementation of the sorting algorithm used by the language's standard library. `O(k)` is also required for the answer array.1 company
Data structures
ArrayHash Table
Companies
X

Prompt

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.

 

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach avoids using a hash map by first sorting the input logs. By sorting the logs, all actions for a single user are grouped together, making it possible to process them sequentially.

Algorithm

  • Sort the logs array. The primary sorting key is ID (log[0]), and the secondary key is time (log[1]).
  • Initialize an integer array result of size k.
  • Iterate through the sorted logs from left to right using an index i.
  • For each user starting at index i:
    • Count the unique minutes. Start a uamCount at 0.
    • Use a second pointer j starting from i to find the end of the current user's logs.
    • While j is within bounds and the user ID is the same, check if logs[j][1] is different from logs[j-1][1] (or if it's the first log for this user). If it is, increment uamCount.
    • After iterating through all of the current user's logs, if uamCount is valid (i.e., 1 <= uamCount <= k), increment result[uamCount - 1].
    • Update the main loop index i to j to start processing the next user.
  • Return result.

Walkthrough

The core idea is to group logs by user ID without using an explicit map. Sorting achieves this. We sort the logs array first by user ID, and for users with the same ID, we sort by the time of action.

After sorting, we can iterate through the sorted array. We process one user at a time. We count the number of unique minutes for the current user by checking for changes in the time value. When we encounter a new user ID, the processing for the previous user is complete. We take their calculated UAM (unique active minutes) and update our final result array. This process continues until all logs have been processed.

import java.util.Arrays; class Solution {    public int[] findingUsersActiveMinutes(int[][] logs, int k) {        // Sort by ID, then by time        Arrays.sort(logs, (a, b) -> {            if (a[0] != b[0]) {                return Integer.compare(a[0], b[0]);            }            return Integer.compare(a[1], b[1]);        });         int[] answer = new int[k];        int n = logs.length;        int i = 0;        while (i < n) {            int currentId = logs[i][0];            int uam = 0;            int j = i;            // Iterate through all logs for the current user            while (j < n && logs[j][0] == currentId) {                // Check for unique minute                if (j == i || logs[j][1] != logs[j - 1][1]) {                    uam++;                }                j++;            }                        if (uam > 0 && uam <= k) {                answer[uam - 1]++;            }                        // Move to the next user            i = j;        }        return answer;    }}

Complexity

Time

O(N log N), where N is the number of logs. The sorting step dominates the complexity. The subsequent linear scan is O(N).

Space

O(log N + k) or O(N + k). The space depends on the implementation of the sorting algorithm used by the language's standard library. `O(k)` is also required for the answer array.

Trade-offs

Pros

  • Can be more space-efficient than a HashMap approach if an in-place sort is used and the number of logs N is much larger than k.

Cons

  • Slower time complexity (O(N log N)) compared to the HashMap approach.

  • Modifies the input array by sorting it, which might not be desirable in some contexts.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem