We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Finding the Users Active Minutes

Number: 1945

Difficulty: Medium

Paid? No

Companies: X

Problem Description

Given a list of logs where each log is a pair [ID, time], you need to compute each user's active minutes (unique minutes they performed an action) and then return a 1-indexed array answer of size k where answer[j] represents the number of users with exactly j active minutes.

Key Insights

  • Use a hash table (or dictionary) to map each user ID to a set of the minutes in which they performed actions.
  • Sets naturally handle duplicate minutes, ensuring that each minute is only counted once per user.
  • After processing the logs, iterate through the dictionary to count the number of users who have a specific number of unique active minutes.
  • Finally, construct the result array of length k (1-indexed) reflecting the count for each possible UAM from 1 to k.

Space and Time Complexity

Time Complexity: O(n), where n is the number of logs (each log is processed once, and set operations are near constant time on average).
Space Complexity: O(n), due to storage for the dictionary mapping user IDs to sets of minutes.

Solution

The solution uses a hash table (or dictionary) to group the logs by user ID. For every log [user, time], add the time to a set associated with that user. This automatically ensures that each minute is counted only once per user.
Once all logs are processed, iterate through the dictionary to compute the number of unique minutes for each user (the size of their set). Then, for each count, increment the corresponding index in the answer array (adjusting since the answer array is 1-indexed).
Finally, return the answer array.

Code Solutions

# Python solution for Finding the Users Active Minutes

def finding_users_active_minutes(logs, k):
    # Dictionary to store user ID to set of unique active minutes
    user_minutes = {}
    
    # Process each log entry
    for user_id, time in logs:
        # Use setdefault to initialize a new set if user_id not in dictionary
        user_minutes.setdefault(user_id, set()).add(time)
    
    # Prepare result array with k zeros (1-indexed answer)
    answer = [0] * k
    
    # For each user, count the unique minutes and update the answer array
    for minutes in user_minutes.values():
        # Get the size of the set i.e., the count of unique minutes
        unique_count = len(minutes)
        # Subtract 1 for zero-based index, but check valid range (unique_count in 1..k)
        if 1 <= unique_count <= k:
            answer[unique_count - 1] += 1
            
    return answer

# Example usage:
logs_example = [[0,5],[1,2],[0,2],[0,5],[1,3]]
k_example = 5
print(finding_users_active_minutes(logs_example, k_example))  # Expected: [0,2,0,0,0]
← Back to All Questions