#1817

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Finding the Users Active Minutes

This problem requires counting unique minutes of user activity on LeetCode based on a series of logs and an integer k.

Problem Statement

You are given a 2D array of logs, where each log contains two integers: the user ID and the minute in which the action was performed. Your task is to compute the number of unique active minutes for each user based on the given logs and an integer k representing the maximum possible active minutes a user can have.

Multiple actions can be performed at the same minute by a single user or by different users, but only unique minutes are counted. You need to return an array where each index corresponds to the number of users with a specific active minute count, from 1 to k.

Examples

Example 1

Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5

Output: [0,2,0,0,0]

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]

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

Solution Approach

Step 1: Group Actions by User

First, we group the logs by user ID, ensuring that we can count the number of unique minutes for each user. Using a hash table is a natural fit for this as it allows us to efficiently store and access each user's actions by minute.

Step 2: Calculate Unique Active Minutes

For each user, we determine the unique minutes they performed actions. This can be achieved by storing the minutes in a set (since sets only store unique values). The size of the set gives the user's active minutes.

Step 3: Count Active Minute Frequencies

We then construct the final result by counting how many users have each possible active minute count (from 1 to k). This is done by iterating through the users' unique active minutes and updating an array that tracks these frequencies.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity primarily depends on the operations for grouping logs by user and counting unique minutes. The overall complexity is O(n), where n is the number of logs, since each log is processed once. Space complexity is O(n) for storing the logs and user activity data, and the result array requires O(k) space where k is the upper limit of active minutes.

What Interviewers Usually Probe

Look for the candidate's ability to efficiently use hash tables for grouping and counting.
Check if the candidate can reason about the use of sets for counting unique minutes.
Evaluate the candidate's understanding of time and space complexity trade-offs in this problem.

Common Pitfalls or Variants

Common pitfalls

Not using a set to count unique minutes, which could lead to over-counting for users with multiple actions at the same minute.
Failing to account for users with zero active minutes (resulting in incorrect array indexing).
Using inefficient data structures or algorithms that lead to unnecessary time complexity.

Follow-up variants

Consider edge cases where all actions occur at the same minute or all users have the same active minute count.
What if the input logs contain many repeated user actions? How would your solution scale?
What if k is smaller than the maximum unique minutes for any user? Can your solution still work within these constraints?

FAQ

How do I approach the 'Finding the Users Active Minutes' problem?

Focus on scanning the logs array while using hash tables to group actions by user. Then, calculate the unique minutes each user was active and count the frequency of these active minute counts.

What data structures are useful for this problem?

Hash tables are crucial for grouping user actions, and sets are helpful for counting unique minutes of activity for each user.

How can I optimize my solution for large input sizes?

Ensure that you process each log entry once, and use efficient data structures like hash tables and sets to minimize unnecessary computation.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of logs, since each log entry is processed once.

What if multiple users perform actions at the same minute?

You count each minute only once per user. The key challenge is to store the unique minutes per user, which can be done using a set for each user.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#1814 count nice pairs in an array #1807 evaluate the bracket pairs of a string #1782 count pairs of nodes