LeetCode 1817 - Finding the Users Active Minutes

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

This problem asks us to analyze a collection of user activity logs and determine how many users have a specific number of unique active minutes.

Each log entry is represented as:

[IDi, timei]

where:

IDi is the user's ID
timei is the minute when that user performed an action

A user may perform multiple actions during the same minute, but repeated actions in the same minute only count once toward that user's active minutes.

The key definition is the User Active Minutes (UAM):

The UAM of a user is the number of distinct minutes during which the user performed at least one action.

After computing the UAM for every user, we must build a result array of length k.

The result is 1-indexed conceptually:

answer[1] represents how many users have exactly 1 active minute
answer[2] represents how many users have exactly 2 active minutes
...
answer[k] represents how many users have exactly k active minutes

Since programming languages use 0-indexed arrays, we usually store the count for UAM j at index j - 1.

Consider the first example:

logs = [[0,5],[1,2],[0,2],[0,5],[1,3]]

User 0 appears at minutes:

5, 2, 5

The unique minutes are:

{2, 5}

so the UAM is 2.

User 1 appears at minutes:

2, 3

which also gives a UAM of 2.

Therefore, two users have UAM equal to 2, so the answer becomes:

[0,2,0,0,0]

The constraints are important:

logs.length <= 10^4
User IDs can be very large, up to 10^9
Time values can also be large

These constraints strongly suggest that we should not use arrays indexed by user ID or time. Instead, hash-based structures such as dictionaries/maps and sets are ideal.

The problem also guarantees that:

k >= maximum UAM of any user

so every user's UAM always fits into the answer array.

Several edge cases are important:

A user may appear many times in the same minute
Multiple users may act during the same minute
Only one user may exist
Every log entry may belong to a distinct minute
k may be larger than the actual maximum UAM

A naive implementation that simply counts log entries per user would fail because duplicate minutes must only be counted once.

Approaches

Brute Force Approach

A brute-force solution would process each user separately and repeatedly scan the entire logs array to collect that user's unique minutes.

One possible implementation would be:

Extract all unique user IDs.
For each user:

Scan every log entry.
Collect that user's minutes into a temporary set.
Compute the set size.

Update the final frequency array.

This works because sets automatically eliminate duplicate minutes, producing the correct UAM for each user.

However, this approach is inefficient because the logs array is scanned repeatedly for every user.

If there are:

n log entries
u unique users

then the complexity becomes approximately:

O(u * n)

In the worst case, every log belongs to a different user, making the complexity close to:

O(n^2)

which is unnecessary for the given constraints.

Optimal Approach

The key observation is that we only need to process each log entry once.

We can maintain:

user_id -> set of unique minutes

As we iterate through the logs:

If a user has not been seen before, create a new set.
Insert the current minute into that user's set.

Because sets automatically ignore duplicates, repeated actions in the same minute do not affect the final count.

After building this structure:

The size of each set equals that user's UAM.
We count how many users have each UAM.
Store those frequencies in the answer array.

This reduces the complexity to linear time relative to the number of logs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(u * n)	O(n)	Repeatedly scans all logs for every user
Optimal	O(n)	O(n)	Uses hash map and sets to track unique minutes efficiently

Algorithm Walkthrough

Create a hash map where:

the key is a user ID
the value is a set of unique active minutes for that user

Iterate through every log entry:

Extract user_id and minute
Insert minute into that user's set

After processing all logs:

Each user's set contains exactly their unique active minutes
The size of the set equals that user's UAM

Create an answer array of size k initialized with zeros.
Iterate through every user's set:

Compute:

uam = len(minutes_set)

Increment:

answer[uam - 1]

because the array is 0-indexed while UAM values start from 1. 6. Return the answer array.

Why it works

The algorithm works because each user's activity minutes are stored in a set, and sets guarantee uniqueness. Therefore, duplicate actions within the same minute are counted only once. After all logs are processed, the size of each set exactly matches that user's UAM. Counting the frequencies of these set sizes directly produces the required answer array.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        user_minutes = defaultdict(set)

        for user_id, minute in logs:
            user_minutes[user_id].add(minute)

        answer = [0] * k

        for minutes_set in user_minutes.values():
            uam = len(minutes_set)
            answer[uam - 1] += 1

        return answer

The implementation begins by creating a defaultdict(set). This is useful because each user automatically gets an empty set the first time they appear.

During the first loop, every (user_id, minute) pair is processed. The minute is inserted into the corresponding user's set. If the same minute appears multiple times for the same user, the set ignores duplicates automatically.

After all logs are processed, the dictionary contains the complete set of unique minutes for every user.

The answer array is initialized with k zeros because we must return exactly k entries.

The second loop iterates through every set of minutes. The size of the set gives the user's UAM. Since the result array is 0-indexed, the count for UAM x is stored at index x - 1.

Finally, the completed frequency array is returned.

Go Solution

func findingUsersActiveMinutes(logs [][]int, k int) []int {
	userMinutes := make(map[int]map[int]bool)

	for _, log := range logs {
		userID := log[0]
		minute := log[1]

		if _, exists := userMinutes[userID]; !exists {
			userMinutes[userID] = make(map[int]bool)
		}

		userMinutes[userID][minute] = true
	}

	answer := make([]int, k)

	for _, minutesSet := range userMinutes {
		uam := len(minutesSet)
		answer[uam-1]++
	}

	return answer
}

The Go implementation uses a nested map structure because Go does not have a built-in set type.

The outer map stores:

userID -> minute set

The inner map acts as a set:

minute -> true

When a minute is inserted multiple times, it simply overwrites the same key, preserving uniqueness.

The rest of the logic matches the Python solution closely.

Unlike Python, Go requires explicit initialization of nested maps before insertion. The solution handles this by checking whether the user's map already exists before adding a minute.

Worked Examples

Example 1

Input:

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

Step-by-step processing

Log Entry	user_minutes State
[0,5]	{0: {5}}
[1,2]	{0: {5}, 1: {2}}
[0,2]	{0: {2,5}, 1: {2}}
[0,5]	{0: {2,5}, 1: {2}}
[1,3]	{0: {2,5}, 1: {2,3}}

Now compute UAM values:

User	Unique Minutes	UAM
0	{2,5}	2
1	{2,3}	2

Initialize:

answer = [0,0,0,0,0]

Process user 0:

answer[1] += 1

Result:

[0,1,0,0,0]

Process user 1:

answer[1] += 1

Final result:

[0,2,0,0,0]

Example 2

Input:

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

Step-by-step processing

Log Entry	user_minutes State
[1,1]	{1: {1}}
[2,2]	{1: {1}, 2: {2}}
[2,3]	{1: {1}, 2: {2,3}}

Compute UAM values:

User	Unique Minutes	UAM
1	{1}	1
2	{2,3}	2

Initialize:

answer = [0,0,0,0]

After processing both users:

[1,1,0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each log entry is processed once
Space	O(n)	Hash map and sets may store all log entries uniquely

The algorithm processes each log exactly once while inserting into hash sets. Hash set insertion is average-case constant time, making the total runtime linear in the number of log entries.

The space complexity is also linear because, in the worst case, every log entry could represent a unique (user, minute) pair that must be stored.

Test Cases

solution = Solution()

# Example 1
assert solution.findingUsersActiveMinutes(
    [[0,5],[1,2],[0,2],[0,5],[1,3]], 5
) == [0,2,0,0,0]  # duplicate minute for user 0

# Example 2
assert solution.findingUsersActiveMinutes(
    [[1,1],[2,2],[2,3]], 4
) == [1,1,0,0]  # one user with UAM 1 and one with UAM 2

# Single user with repeated identical actions
assert solution.findingUsersActiveMinutes(
    [[1,1],[1,1],[1,1]], 3
) == [1,0,0]  # duplicates should count once

# Multiple users, each with one unique minute
assert solution.findingUsersActiveMinutes(
    [[1,1],[2,1],[3,1]], 3
) == [3,0,0]  # all users have UAM 1

# One user with maximum UAM
assert solution.findingUsersActiveMinutes(
    [[1,1],[1,2],[1,3],[1,4]], 4
) == [0,0,0,1]  # single user with UAM 4

# Mixed duplicates and unique values
assert solution.findingUsersActiveMinutes(
    [[1,1],[1,2],[1,2],[2,3],[2,3],[2,4]], 4
) == [0,2,0,0]  # both users have UAM 2

# k larger than maximum UAM
assert solution.findingUsersActiveMinutes(
    [[1,1],[2,2]], 5
) == [2,0,0,0,0]  # trailing zeros required

# Large user IDs
assert solution.findingUsersActiveMinutes(
    [[1000000000,1],[1000000000,2]], 2
) == [0,1]  # verifies hash map handling of large IDs

Test	Why
Example 1	Validates duplicate minute handling
Example 2	Validates multiple UAM counts
Repeated identical actions	Ensures duplicates count once
Multiple users with same minute	Confirms users are independent
Single user with large UAM	Tests higher UAM indexing
Mixed duplicates	Verifies set behavior
Large `k`	Ensures unused positions remain zero
Large user IDs	Confirms hash-based indexing works correctly

Edge Cases

One important edge case occurs when a user performs many actions during the same minute. A naive implementation that simply counts actions would overcount the UAM. For example:

[[1,5],[1,5],[1,5]]

should produce a UAM of 1, not 3. The implementation handles this correctly because sets automatically remove duplicate minute values.

Another important edge case occurs when multiple users act during the same minute. Since UAM is calculated independently per user, identical timestamps across different users must not interfere with each other. The hash map separates data by user ID, ensuring each user's minutes are tracked independently.

A third edge case happens when k is larger than every actual UAM value. The answer array must still contain exactly k entries. The implementation initializes the result array with size k, so any unused frequencies naturally remain zero.

A final subtle edge case involves extremely large user IDs. Since IDs may be as large as 10^9, using arrays indexed by ID would be impractical. The implementation uses hash maps instead, allowing efficient handling of sparse, very large IDs without wasting memory.