Leetcode problem 67 - Finding the Users Active Minutes

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.

/**
 * @param {number[][]} logs
 * @param {number} k
 * @return {number[]}
 */
var findingUsersActiveMinutes = function (logs, k) {
  // Initialize a map to store unique minutes for each user and an array to store the answers.
  let map = new Map();
  const answers = new Array(k).fill(0);

  // Iterate through the log entries to process each user's actions.
  for (const [id, time] of logs) {
    // Check if the user is already in the map; if not, create a new Set to store unique minutes.
    if (!map.has(id)) {
      map.set(id, new Set());
    }
    // Add the current action's minute to the user's Set.
    map.get(id).add(time);
  }

  // Iterate through the Sets in the map, calculate the User Active Minutes (UAM), and update the answers array.
  for (const times of map.values()) {
    const uam = times.size;
    answers[uam - 1]++;
  }

  // Return the array of answers
  return answers;
};

The time complexity of the “findingUsersActiveMinutes” function is O(N), where N is the number of log entries in the “logs” array. This is because the function iterates through the log entries once to create a map of unique minutes for each user, and then iterates through the map values to calculate the user active minutes and update the “answers” array. Both loops have a linear time complexity, and there are no nested loops, making the overall time complexity linear in terms of the number of log entries.