1817. Finding the Users Active Minutes

Problem Description

In this problem, we are dealing with logs of user actions on LeetCode. The logs are given as a 2-dimensional array where each element represents a user's action with two pieces of information: the user's ID and the time the action occurred, recorded by the minute. We are instructed to compute a user's active minutes (UAM), which are the unique minutes during which they performed any actions. Importantly, even if a user performs multiple actions within a single minute, that minute is only counted once for their UAM.

Our goal is to create an array of size k, where each entry j indicates the number of users whose UAM is exactly j. To clarify, the array we are constructing is 1-indexed, meaning that the index of each item starts at 1, not 0. Therefore, for every number of active minutes that a user could have (from 1 to k), we want to count how many users have that amount of UAM.

Intuition

The natural approach to solve this problem relies on representing each user's actions without duplications and counting their active minutes efficiently. Since a user can perform many actions, possibly at the same times, we need a way to store these actions such that we can easily determine the unique minutes.

Using a hash table, or in Python, a dictionary that maps each user ID to a set of unique times, provides an effective solution. Sets are useful here because they naturally eliminate duplicate entries, which aligns perfectly with counting unique active minutes.

After populating the hash table with each user's unique active minutes, we then need to determine the number of users for each possible UAM value up to k. We accomplish this by initiating an answer array ans filled with zeroes to correspond to counts for each UAM from 1 to k. We loop through the hash table and increment the count in ans at the index that corresponds to the user's UAM (adjusted by subtracting 1 for 1-indexing).

The reason behind this approach is two-fold:

1. By mapping users to sets of timestamps, we efficiently record user activity without duplication, directly giving us the UAM for each user.
2. By using an array indexed by active minutes, we can simply tally up the number of users for each UAM, which the problem requires us to report.

Solution Approach

The solution's strategy is based on the hash table data structure which is very common for storing relationships between key-value pairs. In Python, this is typically implemented using a defaultdict which is a subclass of the dictionary (dict). A defaultdict allows us to specify a default value for the dictionary – in this case, a set. The set is chosen as the default value because we are interested in keeping a collection of unique active minutes for each user.

Here's the detailed implementation flow:

• Initialize the defaultdict: We create d as a defaultdict of sets. Each user ID will be a key, and the corresponding value will be a set that contains all unique minutes during which the user performed actions.

• Populate the defaultdict:

  • Iterate over each entry in the logs array.
  • For each [user_id, timestamp] pair, add timestamp to the set mapped to by user_id. The set ensures that if the same timestamp is inserted multiple times, it will only be stored once, preserving the unique nature of the active minutes.

• Initiate the ans array: We create an array (list in Python) called ans with length k, filled with zeros. Each index i in this array represents the number of users whose UAM is i + 1, because the problem asks for a 1-indexed array.

• Count the UAM for each user:

  • Loop through the sets in the defaultdict values, which each represent the set of unique active minutes for a particular user ID.
  • The size of each set is the UAM count for that user. Subtracting 1 from the set size gives the index that corresponds to that UAM in the ans array.
  • Increment the value at the calculated index in ans by 1.

By following this solution approach, we effectively tabulate the distribution of UAMs across all users. Finally, we return the populated ans array as our result, which contains the count of users for each UAM value from 1 to k.

Here's an illustration of the reference solution approach in a concise form:

1class Solution:
2    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
3        d = defaultdict(set) # Create defaultdict of sets
4        for i, t in logs:
5            d[i].add(t) # Populate the defaultdict
6        ans = [0] * k # Initialize ans list
7        for ts in d.values():
8            ans[len(ts) - 1] += 1 # Count UAM and populate ans
9        return ans

Example Walkthrough

Let's consider an example to illustrate the solution approach with the logs array and k value as follows:

1logs = [[1, 1], [2, 2], [2, 2], [2, 3], [3, 4], [3, 4], [3, 4], [3, 5]], k = 3

With this data, we'll walk through the implementation steps:

Initialize the defaultdict

We create a defaultdict named d. Each key will be unique user IDs, and each value will be a set of unique timestamps:

1d = defaultdict(set)

Initially, d will be empty.

Populate the defaultdict

We iterate through each log entry and update d with unique active minutes for each user:

• First log entry is [1, 1]—we add minute 1 to user 1's set.
• Next, we process three log entries for user 2. They are all in minutes 2 and 3, resulting in user 2's set containing {2, 3}.
• Lastly, user 3 has entries at minutes 4 and 5, all duplicates, so user 3's set will only contain {4, 5}.

After processing, d looks like this:

1{1: {1}, 2: {2, 3}, 3: {4, 5}}

Initiate the ans array

K is 3, so we create an answer list ans of length k, with all elements initialized to 0:

1ans = [0] * 3 # Which is [0, 0, 0]

Count the UAM for each user

We'll iterate through the sets in defaultdict values and update the ans list based on the number of unique active minutes for each user:

• User 1 has a UAM count of 1, so we increment ans[0] from 0 to 1 (because index 0 corresponds to UAM 1).
• User 2 has a UAM count of 2, so we increment ans[1] to 1.
• User 3 also has a UAM of 2, so we increase ans[1] again, from 1 to 2.

After processing, the ans array is:

1[1, 2, 0]

This array means there is one user with a UAM of 1, two users with a UAM of 2, and zero users with a UAM of 3.

The final output of the reference solution for our given logs and k values would be [1, 2, 0].

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the logs array. This is because we iterate over each element of the logs array exactly once, adding the timestamp to a set in the dictionary. Since set operations such as .add() have a time complexity of O(1), iterating over the logs array contributes O(n) to the time complexity.

Further, we also iterate over the values of the dictionary, with the number of values being at most n. For each of the values, we increment the appropriate count in the ans array, which is another O(1) operation. Hence, the total time complexity remains O(n).

The space complexity of the code is also O(n) because in the worst-case scenario, each log entry could be for a unique user and a unique timestamp, leading to n unique entries in the dictionary. As such, both the dictionary and the set of timestamps could potentially grow linearly with the number of log entries. Therefore, the space used by the dictionary is proportional to the size of the logs array, n.

Learn more about how to find time and space complexity quickly using problem constraints.