3793. Find Users with High Token Usage Solution

The problem

Table: prompts

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| user_id     | int     |
| prompt      | varchar |
| tokens      | int     |
+-------------+---------+
(user_id, prompt) is the primary key (unique value) for this table.
Each row represents a prompt submitted by a user to an AI system along with the number of tokens consumed.

Write a solution to analyze AI prompt usage patterns based on the following requirements:

For each user, calculate the total number of prompts they have submitted.
For each user, calculate the average tokens used per prompt (Rounded to 2 decimal places).
Only include users who have submitted at least 3 prompts.
Only include users who have submitted at least one prompt with tokens greater than their own average token usage.

Return the result table ordered by average tokens in descending order, and then by user_id in ascending order.

The result format is in the following example.

Example:

Input:

prompts table:

+---------+--------------------------+--------+
| user_id | prompt                   | tokens |
+---------+--------------------------+--------+
| 1       | Write a blog outline     | 120    |
| 1       | Generate SQL query       | 80     |
| 1       | Summarize an article     | 200    |
| 2       | Create resume bullet     | 60     |
| 2       | Improve LinkedIn bio     | 70     |
| 3       | Explain neural networks  | 300    |
| 3       | Generate interview Q&A   | 250    |
| 3       | Write cover letter       | 180    |
| 3       | Optimize Python code     | 220    |
+---------+--------------------------+--------+

Output:

+---------+---------------+------------+
| user_id | prompt_count  | avg_tokens |
+---------+---------------+------------+
| 3       | 4             | 237.5      |
| 1       | 3             | 133.33     |
+---------+---------------+------------+

Explanation:

User 1:
- Total prompts = 3
- Average tokens = (120 + 80 + 200) / 3 = 133.33
- Has a prompt with 200 tokens, which is greater than the average
- Included in the result
User 2:
- Total prompts = 2 (less than the required minimum)
- Excluded from the result
User 3:
- Total prompts = 4
- Average tokens = (300 + 250 + 180 + 220) / 4 = 237.5
- Has prompts with 300 and 250 tokens, both greater than the average
- Included in the result

The Results table is ordered by avg_tokens in descending order, then by user_id in ascending order

Approach overview

Problem Overview: You get a table of token usage records, one row per event, each tagged with a user. Return the users whose aggregated token usage meets the condition in the problem statement. The core task is grouping rows by user and filtering the groups.

Approach 1: Nested Scan Per User (O(n * u) Time, O(u) Space)

Collect the distinct users first. For each user, scan the full record set and sum that user's tokens. Compare the sum against the threshold and keep the user if it qualifies. This works, but every user triggers a full pass over the data. With n records and u distinct users, you pay O(n * u) time. Use this only to confirm your logic on small inputs or to explain the naive idea before optimizing.

Approach 2: Group By Aggregation with HAVING (O(n) Time, O(u) Space)

Group the rows by user_id and compute SUM(tokens) for each group in a single pass. Store one running total per user in a hash map, which is exactly what the database or Pandas does internally. Then filter the groups with HAVING in SQL, or a boolean mask on the aggregated frame in Pandas. Each row is read once, so the time is O(n). The extra memory is one entry per distinct user, so the space is O(u). This is the approach to write in an interview and the one that scales.

Recommended for interviews: Interviewers expect Approach 2. The nested scan shows you understand the problem, but the single-pass aggregation shows you know how to reduce work to one pass with a hash map and a filter step. In SQL, the whole solution is a GROUP BY with a HAVING clause. Explain why the filter goes in HAVING and not WHERE: the condition applies to the aggregate, not to individual rows. See hash table and database problems for more practice with this pattern.

Solution

Thinking

We need each user's prompt count, mean token usage, and whether any prompt exceeds that mean. Aggregating those three statistics by user_id, we keep users with at least three prompts and max>mean, then sort by mean tokens and user id.

We first group the prompts by user_id and calculate for each user the total number of prompts prompt_count, the average tokens avg_tokens, and the maximum tokens max_tokens. Then we filter users who meet the criteria, i.e., those who have submitted at least 3 prompts and have at least one prompt with tokens greater than their average token usage. Finally, we sort the results by avg_tokens in descending order and by user_id in ascending order.

MySQL

# Write your MySQL query statement below
SELECT
    user_id,
    COUNT(1) AS prompt_count,
    ROUND(AVG(tokens), 2) AS avg_tokens
FROM prompts
GROUP BY user_id
HAVING prompt_count >= 3 AND MAX(tokens) > AVG(tokens)
ORDER BY avg_tokens DESC, user_id;

Pandas

import pandas as pd


def find_users_with_high_tokens(prompts: pd.DataFrame) -> pd.DataFrame:
    df = prompts.groupby("user_id", as_index=False).agg(
        prompt_count=("user_id", "size"),
        avg_tokens=("tokens", "mean"),
        max_tokens=("tokens", "max"),
    )

    df = df[(df["prompt_count"] >= 3) & (df["max_tokens"] > df["avg_tokens"])]
    df["avg_tokens"] = df["avg_tokens"].round(2)

    df = (
        df.sort_values(["avg_tokens", "user_id"], ascending=[False, True])
        .loc[:, ["user_id", "prompt_count", "avg_tokens"]]
        .reset_index(drop=True)
    )

    return df

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Nested Scan Per User	O(n * u)	O(u)	Small inputs or explaining the naive idea
Group By Aggregation with HAVING	O(n)	O(u)	General case and interviews

Frequently asked questions

Is Find Users with High Token Usage easy or hard?

It is an easy problem with a 58.2% acceptance rate. The core idea is a standard group-and-filter pattern, so once you know GROUP BY with HAVING or a hash map aggregation, the solution is short. Most difficulty comes from remembering to filter on the aggregate, not on individual rows.

Find Users with High Token Usage Python/Java solution?

In Python, use pandas: group the DataFrame by user_id, aggregate the token column with sum, then filter the result with a boolean condition on the threshold. In Java, use a HashMap<Integer, Long> to accumulate totals in a loop, then collect the keys whose values meet the threshold. Both run in O(n) time.

How to solve Find Users with High Token Usage in O(n)?

Use a hash map keyed by user ID. For each row, add its token count to that user's running total. After one pass, keep only the users whose totals meet the threshold. In SQL, this is a GROUP BY user_id with a HAVING clause on SUM(tokens).

What is the best approach for Find Users with High Token Usage?

The best approach is a single-pass GROUP BY aggregation. Group the rows by user, sum the tokens per group, and filter the groups with HAVING in SQL or a boolean mask in Pandas. It runs in O(n) time with O(u) extra space, where u is the number of distinct users.

What data structure is used in Find Users with High Token Usage?

The main data structure is a hash map (or the equivalent grouping structure inside the database engine) that maps each user to a running token total. The filter step then runs over these aggregated entries, not over the raw rows.

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

The optimal solution runs in O(n) time, where n is the number of usage records, because each row is read once. The naive approach of scanning all records for each user takes O(n * u) time. The aggregation stores one total per user, so the extra space is O(u).

Find Users with High Token Usage solution and explanation