Alex Sikorski

Jul 12, 2022

Finding the Users Active Minutes (LeetCode #1817)

The problem can be found here.

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. 1 <= logs.length <= 104
2. 0 <= IDi <= 109
3. 1 <= timei <= 105
4. k is in the range [The maximum UAM for a user, 105].

Initial Thoughts

As the input logs is a 2D array and the second dimension is a fixed size, we do not have to iterate through the second dimension. We can obtain desired values by indexing 0 or 1 where 0 is the ID and 1 is the time.

The problem wants us to find the number of unique minutes where the user performed an action. This is a clear indication that we will have to use HashMap where the key will be the ID AKA nums[i][0]. The value of the entry would have to be a HashSet since the problem is asking for unique times per user. Essentially, a HashMap allows us to track these actions per user and the HashSet prevents us from adding duplicates, which will lead to only unique times being added.

Finally, with a populated HashMap of unique times per user, we can increment the values of an int[] array of size k where the index is dictated by the size of the HashSet for each user.

Solution

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        
        HashMap<Integer, HashSet<Integer>> hashMap = new HashMap<>();
        // create HashMap with ID:[unique times]
        
        for(int[] action : logs){
            // iterate through actions
            HashSet<Integer> set = hashMap.getOrDefault(action[0], null);
            // get set respective to ID, if doesn't exit create null
            if(set == null){
                // if set doesnt exist (new entry) create new set
                set =  new HashSet<>();
                set.add(action[1]);
                hashMap.put(action[0], set);
                // add time stamp to set
            }
            else set.add(action[1]);
                // if set is instantiated, just add the time stamp 
        }
        
        int[] answer = new int[k];
        
        // finally iterate through the values and append (ID not needed)
        for(var UAMs : hashMap.values()){
            answer[UAMs.size() - 1]++;
        }
        return answer;
    }
}

Result