# Finding the Users Active Minutes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/finding-the-users-active-minutes)
Canonical: https://scaleengineer.com/dsa/problems/finding-the-users-active-minutes
**Data structures:** Array, Hash Table
**Companies:** [X](https://scaleengineer.com/companies/x)
---
## Problem
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 <= logs.length <= 104`
* `0 <= IDi <= 109`
* `1 <= timei <= 105`
* `k` is in the range `[The maximum **UAM** for a user, 105]`.

# Approaches
## Approach 1: Sorting
This approach avoids using a hash map by first sorting the input logs. By sorting the logs, all actions for a single user are grouped together, making it possible to process them sequentially.
**Time:** O(N log N), where N is the number of logs. The sorting step dominates the complexity. The subsequent linear scan is O(N). · **Space:** O(log N + k) or O(N + k). The space depends on the implementation of the sorting algorithm used by the language's standard library. `O(k)` is also required for the answer array.
**Pros:** Can be more space-efficient than a HashMap approach if an in-place sort is used and the number of logs `N` is much larger than `k`.
**Cons:** Slower time complexity (`O(N log N)`) compared to the HashMap approach.; Modifies the input array by sorting it, which might not be desirable in some contexts.
### Explanation
The core idea is to group logs by user ID without using an explicit map. Sorting achieves this. We sort the `logs` array first by user ID, and for users with the same ID, we sort by the time of action.

After sorting, we can iterate through the sorted array. We process one user at a time. We count the number of unique minutes for the current user by checking for changes in the time value. When we encounter a new user ID, the processing for the previous user is complete. We take their calculated UAM (unique active minutes) and update our final result array. This process continues until all logs have been processed.

```java
import java.util.Arrays;

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        // Sort by ID, then by time
        Arrays.sort(logs, (a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int[] answer = new int[k];
        int n = logs.length;
        int i = 0;
        while (i < n) {
            int currentId = logs[i][0];
            int uam = 0;
            int j = i;
            // Iterate through all logs for the current user
            while (j < n && logs[j][0] == currentId) {
                // Check for unique minute
                if (j == i || logs[j][1] != logs[j - 1][1]) {
                    uam++;
                }
                j++;
            }
            
            if (uam > 0 && uam <= k) {
                answer[uam - 1]++;
            }
            
            // Move to the next user
            i = j;
        }
        return answer;
    }
}
```
### Algorithm
*   Sort the `logs` array. The primary sorting key is `ID` (`log[0]`), and the secondary key is `time` (`log[1]`).
*   Initialize an integer array `result` of size `k`.
*   Iterate through the sorted `logs` from left to right using an index `i`.
*   For each user starting at index `i`:
    *   Count the unique minutes. Start a `uamCount` at 0.
    *   Use a second pointer `j` starting from `i` to find the end of the current user's logs.
    *   While `j` is within bounds and the user ID is the same, check if `logs[j][1]` is different from `logs[j-1][1]` (or if it's the first log for this user). If it is, increment `uamCount`.
    *   After iterating through all of the current user's logs, if `uamCount` is valid (i.e., `1 <= uamCount <= k`), increment `result[uamCount - 1]`.
    *   Update the main loop index `i` to `j` to start processing the next user.
*   Return `result`.

## Approach 2: Using HashMap
This approach uses a hash map to efficiently group user activities and a hash set to count unique minutes for each user. This is the most direct and time-efficient way to solve the problem.
**Time:** O(N + U), where N is the number of logs and U is the number of unique users. This simplifies to O(N) because U <= N. Populating the map takes O(N) time (assuming O(1) hash operations). Iterating through the U unique users takes O(U) time. · **Space:** O(M + k), where `M` is the total number of unique user-minute pairs across all logs, and `k` is the size of the result array. In the worst case, `M` can be equal to `N` (if all logs are unique). So, the space complexity is O(N + k).
**Pros:** Optimal time complexity of O(N).; Conceptually straightforward and easy to implement.; Does not modify the input array.
**Cons:** Uses more space than the sorting approach, which could be a factor if memory is extremely constrained and `N` is very large.
### Explanation
The problem requires us to find the number of unique minutes per user. A `HashMap` is an ideal data structure for this task. We can map each `userID` to a data structure that stores the unique minutes of their activity.

A `HashSet` is perfect for storing these unique minutes, as it automatically handles duplicates. So, the main data structure will be a `HashMap<Integer, HashSet<Integer>>`.

We first iterate through all the `logs`. For each log `[id, time]`, we find the corresponding user's entry in the map. We then add the `time` to the user's `HashSet` of active minutes.

After processing all logs, the map will contain every user and the set of unique minutes they were active. The size of each `HashSet` gives the UAM for that user. Finally, we iterate through the map's values (the `HashSet`s), get their sizes, and populate the final `answer` array.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Map<Integer, Set<Integer>> userActivityMap = new HashMap<>();

        for (int[] log : logs) {
            int id = log[0];
            int time = log[1];
            userActivityMap.computeIfAbsent(id, key -> new HashSet<>()).add(time);
        }

        int[] answer = new int[k];
        for (Set<Integer> minutes : userActivityMap.values()) {
            int uam = minutes.size();
            if (uam > 0 && uam <= k) {
                answer[uam - 1]++;
            }
        }

        return answer;
    }
}
```
### Algorithm
*   Create a `HashMap<Integer, HashSet<Integer>>` named `userActivityMap`.
*   Iterate through each `log` in the `logs` array:
    *   Let `id = log[0]` and `time = log[1]`.
    *   Use `map.computeIfAbsent(id, k -> new HashSet<>())` to get the set for the current user, creating a new one if it doesn't exist.
    *   Add `time` to this set. The `HashSet` automatically handles duplicate minutes.
*   Initialize an integer array `answer` of size `k`.
*   Iterate through each `HashSet` (value) in the `userActivityMap`:
    *   Let `uam = set.size()`.
    *   If `uam` is between 1 and `k` (inclusive), increment `answer[uam - 1]`.
*   Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  int[] findingUsersActiveMinutes(int[][] logs, int k) {
    Map<Integer, Set<Integer>> d = new HashMap<>();
    for (var log : logs) {
      int i = log[0], t = log[1];
      d.computeIfAbsent(i, key->new HashSet<>()).add(t);
    }
    int[] ans = new int[k];
    for (var ts : d.values()) {
      ++ans[ts.size() - 1];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findingUsersActiveMinutes(vector<vector<int>> &logs, int k) {
    unordered_map<int, unordered_set<int>> d;
    for (auto &log : logs) {
      int i = log[0], t = log[1];
      d[i].insert(t);
    }
    vector<int> ans(k);
    for (auto &[_, ts] : d) {
      ++ans[ts.size() - 1];
    }
    return ans;
  }
};

```

### Python

```python
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

```