How do you solve Find Users with High Token Usage on LeetCode?

Find Users with High Token Usage (LeetCode #3793) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Users with higher token usage often have more prompts.

What is the time complexity of Find Users with High Token Usage?

The optimal solution for Find Users with High Token Usage runs in O(n) time and uses O(n) space. Single pass for counting and averaging reduces the complexity to linear.

What is the brute force solution for Find Users with High Token Usage?

The brute force approach for Find Users with High Token Usage is Brute Force, with O(n²) time complexity and O(1) space complexity. Calculate total prompts and average tokens for each user by iterating through the entire dataset multiple times. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Find Users with High Token Usage?

Clarify requirements before coding. Discuss edge cases like users with exactly 3 prompts. Explain your thought process while coding.

What are common mistakes when solving Find Users with High Token Usage?

Not rounding the average tokens correctly. Ignoring users with exactly 3 prompts.

#3793

Find Users with High Token Usage

Easy

Hash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Use a single pass to compute total prompts and tokens, then filter users based on conditions in a second pass. This reduces the time complexity significantly.

⚙️

Algorithm

3 steps

1Step 1: Use a dictionary to count prompts and sum tokens for each user.
2Step 2: Calculate average tokens for each user.
3Step 3: Filter users based on the criteria and sort the results.

solution.py12 lines

1WITH UserStats AS (
2    SELECT user_id, COUNT(prompt) AS total_prompts, ROUND(AVG(tokens), 2) AS avg_tokens
3    FROM prompts
4    GROUP BY user_id
5    HAVING total_prompts >= 3
6)
7SELECT us.user_id, us.avg_tokens
8FROM UserStats us
9WHERE EXISTS (
10    SELECT 1 FROM prompts p WHERE p.user_id = us.user_id AND p.tokens > us.avg_tokens
11)
12ORDER BY us.avg_tokens DESC, us.user_id ASC;

ℹ

Complexity note: Single pass for counting and averaging reduces the complexity to linear.

1Users with higher token usage often have more prompts.
2Filtering based on average tokens helps identify outliers.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.