Finding the Users Active Minutes

Medium

Asked by:

12 views

Topics:

ArraysArrays

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 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 <= 10⁴
0 <= ID_i <= 10⁹
1 <= time_i <= 10⁵
k is in the range [The maximum UAM for a user, 10⁵].

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the user IDs and the minutes they are active?
Can a user have the same minute reported multiple times; if so, should that minute be counted only once for that user?
Is the input guaranteed to be valid, or should I handle cases like an empty logs array or an invalid k value?
What should the output array contain if no user has exactly 'k' active minutes?
Could you provide a more concrete example if k is larger than the number of active minutes for a given user?

Brute Force Solution

Approach

The brute force strategy for calculating active minutes involves checking every single activity record for each user. We'll meticulously track each user's unique active minutes by going through the entire set of records.

Here's how the algorithm would work step-by-step:

Start with an empty record for each user to track their active minutes.
Look at the first activity record.
Note the user and the minute they were active.
If this minute is new for that user, count it as an active minute.
Repeat this process for every activity record.
Once you've gone through all activity records, you'll have the total count of unique active minutes for each user.
Finally, count how many users have each possible number of active minutes, for example, how many users have exactly 1 active minute, 2 active minutes, and so on, up to the maximum allowed.

Code Implementation

def finding_users_active_minutes(logs, k):
    user_activity = {}

    # Iterate through each log entry.
    for log_entry in logs:
        user_id, minute = log_entry

        # Initialize the user's active minutes set if not already present
        if user_id not in user_activity:
            user_activity[user_id] = set()

        # Add the minute to the user's set of active minutes.
        user_activity[user_id].add(minute)

    # Initialize the result array with counts for each possible active minute.
    active_minute_counts = [0] * k

    # Count the number of users with each number of active minutes.
    for user_id in user_activity:

        #Determine the user's total active minutes
        total_active_minutes = len(user_activity[user_id])

        # Increment the corresponding count in the result array.
        if total_active_minutes <= k:
            active_minute_counts[total_active_minutes - 1] += 1

    return active_minute_counts

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each activity record once, where 'n' is the number of activity records. For each record, it performs a constant-time operation to check if the minute is new for the user and updates the user's active minute count if needed. Therefore, the time complexity is directly proportional to the number of activity records, resulting in O(n).

Space Complexity

O(U*M) – The algorithm uses a data structure to store each user's unique active minutes. In the worst case, each user could have a different set of active minutes. Therefore, we potentially need to store a set of unique minutes for each user, where U is the number of users and M is the maximum possible value of the active minute. The auxiliary space grows linearly with both the number of users (U) and the range of possible active minutes (M). Thus, the space complexity is O(U*M).

Optimal Solution

Approach

The goal is to figure out how many users were active for exactly 1 minute, 2 minutes, 3 minutes, and so on. We can efficiently track user activity times using a temporary record and then count how many users had each activity level.

Here's how the algorithm would work step-by-step:

First, create a temporary record for each user to store the unique minutes they were active.
Go through the list of activity logs and for each log, add the minute to the corresponding user's record. Be sure to only include each unique minute of activity for a user once.
Next, create a way to count how many users were active for a specific number of minutes.
For each user, count the number of unique minutes in their record. This is their total active minutes.
Update the counts by noting how many users had 1 active minute, how many had 2, and so on.
Finally, report the number of users for each amount of active minutes as the answer.

Code Implementation

def finding_users_active_minutes(logs, k):
    user_activities = {}

    # We iterate through logs to record user activity.
    for user_id, activity_time in logs:
        if user_id not in user_activities:
            user_activities[user_id] = set()

        user_activities[user_id].add(activity_time)

    active_minutes_counts = [0] * k

    # Now we count users with specific active minute counts.
    for user_id in user_activities:
        active_minutes = len(user_activities[user_id])

        # Adjust counts for users' active minutes.
        if active_minutes <= k:
            active_minutes_counts[active_minutes - 1] += 1

    return active_minutes_counts

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of logs in the input array logs. The first loop iterates through each log entry in the logs array to record user activity. The operations inside the loop (accessing a hashmap and set insertion) take constant time. The next loop iterates through the users and their active minutes. The number of users is at most n, and the set size for each user is also bounded by n, but given we are calculating active minutes for each user, and there can be at most n users, we can safely say this is linear. Finally, reporting the result takes constant time. Therefore, the dominant operation is the initial loop, which iterates through the n logs; thus, the overall time complexity is O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from creating a temporary record for each user to store the unique minutes they were active. In the worst-case scenario, each user could have a different minute of activity in every activity log. If N is the number of logs, in the worst case the temporary records could store N unique minutes across all users. Thus, the auxiliary space grows linearly with the number of logs. This results in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty logs array	Return an array of zeros with length equal to k, indicating no active minutes for any user.
k is zero or negative	Treat k as 1, since the problem implies at least one active minute is possible and array sizing wouldn't make sense otherwise.
A user has more than one entry for the same minute.	Treat multiple entries for the same user and minute as a single active minute.
All users have zero active minutes.	Return an array of zeros with length equal to k.
All users have exactly the same number of active minutes.	The output array will have a single non-zero value at the index corresponding to that number of active minutes.
user id or minute is negative	Convert the user id and minutes to its absolute value, or throw an error if negative values are not supported.
Extremely large user IDs or minutes (potential integer overflow).	Use appropriate data types (e.g., long) to handle potentially large values and prevent integer overflow.
Logs are sorted by user and then minute, or logs are completely unsorted	The solution should work regardless of log order, as the hashmap or set approach will handle both sorted and unsorted scenarios.

Null or empty logs array

How to Handle:

Return an array of zeros with length equal to k, indicating no active minutes for any user.

k is zero or negative

How to Handle:

Treat k as 1, since the problem implies at least one active minute is possible and array sizing wouldn't make sense otherwise.

A user has more than one entry for the same minute.

How to Handle:

Treat multiple entries for the same user and minute as a single active minute.

All users have zero active minutes.

How to Handle:

Return an array of zeros with length equal to k.

All users have exactly the same number of active minutes.

How to Handle:

The output array will have a single non-zero value at the index corresponding to that number of active minutes.

user id or minute is negative

How to Handle:

Convert the user id and minutes to its absolute value, or throw an error if negative values are not supported.

Extremely large user IDs or minutes (potential integer overflow).

How to Handle:

Use appropriate data types (e.g., long) to handle potentially large values and prevent integer overflow.

Logs are sorted by user and then minute, or logs are completely unsorted

How to Handle:

The solution should work regardless of log order, as the hashmap or set approach will handle both sorted and unsorted scenarios.