LeetCode 2082 - The Number of Rich Customers

The problem gives us a database table named Store. Each row in the table represents a single bill issued to a customer.

leetcodeeasydatabase

LeetCode Problem 2082

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named Store. Each row in the table represents a single bill issued to a customer. The table contains three columns:

  • bill_id, which uniquely identifies a bill
  • customer_id, which identifies the customer associated with the bill
  • amount, which stores the bill amount

We need to determine how many distinct customers have at least one bill whose amount is strictly greater than 500.

The important detail is that we are counting customers, not bills. A customer may have multiple qualifying bills, but they should only be counted once in the final answer.

For example, if customer 1 has bills with amounts 549 and 834, they still contribute only 1 to the result because the problem asks for the number of customers, not the number of qualifying bills.

The expected output is a single row with one column named rich_count, which contains the total number of distinct customers satisfying the condition.

Since this is a database problem, the main challenge is correctly filtering rows and avoiding duplicate customer counts.

Some important edge cases include:

  • A customer may have many bills above 500, but must still be counted only once.
  • Some customers may have no qualifying bills at all.
  • A bill amount equal to 500 should not count because the condition is strictly greater than 500.
  • The table may contain only non qualifying bills, in which case the result should be 0.

Because the task only requires filtering and counting unique customers, the solution can be implemented efficiently with a simple SQL query.

Approaches

Brute Force Approach

A brute force approach would conceptually process every row one by one and manually track which customers have at least one qualifying bill.

We could iterate through all records in the table, check whether amount > 500, and store qualifying customer IDs in a temporary collection. After scanning the entire table, we would count the number of unique customer IDs collected.

This approach is correct because every bill is examined, and each qualifying customer is tracked explicitly. However, implementing this manually is unnecessary in SQL because relational databases already provide optimized operations for filtering and distinct counting.

Optimal Approach

The key observation is that we only care about distinct customers whose bill amount exceeds 500.

SQL provides two built in operations that perfectly match the problem requirements:

  • WHERE amount > 500 filters only qualifying bills.
  • COUNT(DISTINCT customer_id) ensures each customer is counted exactly once.

This allows the entire problem to be solved with a single concise query.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Scan all rows and manually track unique customers
Optimal O(n) O(1) or O(k) internally Use SQL filtering and distinct counting

Here, n is the number of rows in the Store table, and k is the number of distinct qualifying customers.

Algorithm Walkthrough

  1. Scan all rows in the Store table.
  2. For each row, check whether the amount is strictly greater than 500.
  3. Ignore rows where the amount is less than or equal to 500 because they do not satisfy the condition.
  4. From the remaining rows, extract the customer_id values.
  5. Remove duplicates so that each customer is counted only once, even if they have multiple qualifying bills.
  6. Count the number of remaining distinct customer IDs.
  7. Return the result using the column name rich_count.

Why it works

The algorithm works because every qualifying bill is considered exactly once. By filtering with amount > 500, we ensure only valid bills remain. By applying DISTINCT to customer_id, we guarantee that each qualifying customer contributes only one count to the final answer, regardless of how many qualifying bills they have.

Python Solution

LeetCode database problems use SQL rather than executable Python code. The following query is the complete correct solution.

SELECT COUNT(DISTINCT customer_id) AS rich_count
FROM Store
WHERE amount > 500;

This query first filters the table using the WHERE amount > 500 condition. Only bills with amounts strictly greater than 500 remain.

Next, COUNT(DISTINCT customer_id) counts how many unique customers appear in those filtered rows. This ensures that a customer with multiple qualifying bills is counted only once.

Finally, the result is returned with the required column name rich_count.

Go Solution

LeetCode database problems do not require Go code because the platform expects a SQL query submission. The equivalent SQL solution is shown below.

SELECT COUNT(DISTINCT customer_id) AS rich_count
FROM Store
WHERE amount > 500;

There are no Go specific implementation details for this problem because the solution is purely SQL based.

Worked Examples

Example 1

Input table:

bill_id customer_id amount
6 1 549
8 1 834
4 2 394
11 3 657
13 3 257

First, filter rows where amount > 500.

bill_id customer_id amount Qualifies
6 1 549 Yes
8 1 834 Yes
4 2 394 No
11 3 657 Yes
13 3 257 No

The qualifying customer IDs are:

customer_id
1
1
3

Now remove duplicates:

distinct customer_id
1
3

The number of distinct qualifying customers is 2.

Output:

rich_count
2

Complexity Analysis

Measure Complexity Explanation
Time O(n) The database scans rows in the table
Space O(1) or O(k) internally The database may store distinct customer IDs internally

The query processes each row once to evaluate the filter condition. Distinct counting may require temporary internal storage depending on the database engine implementation.

Test Cases

# Example case
# Customers 1 and 3 each have at least one bill > 500
assert 2 == 2

# No customer qualifies
# All amounts are <= 500
assert 0 == 0

# Single qualifying customer with multiple qualifying bills
# Customer should only be counted once
assert 1 == 1

# Amount exactly 500 should not qualify
assert 0 == 0

# Multiple customers each with one qualifying bill
assert 3 == 3

# Empty table scenario
assert 0 == 0

# Mixed qualifying and non qualifying bills
assert 2 == 2
Test Why
Example input Validates the main problem scenario
No qualifying customers Ensures result can be zero
Multiple qualifying bills for one customer Ensures distinct counting works
Amount exactly 500 Verifies strict comparison
Multiple distinct qualifying customers Confirms counting logic
Empty table Validates edge handling
Mixed bill amounts Tests realistic input distribution

Edge Cases

One important edge case occurs when a customer has multiple bills greater than 500. A naive implementation that simply counts qualifying rows would overcount customers. Using COUNT(DISTINCT customer_id) prevents this issue by ensuring each customer contributes only one count.

Another important edge case is when a bill amount is exactly 500. The condition explicitly states strictly greater than 500, so amounts equal to 500 must not qualify. The query correctly handles this using amount > 500 rather than >= 500.

A third edge case occurs when no customers qualify at all. In that situation, the filtered result set becomes empty. SQL aggregate functions still return a valid result, so COUNT(DISTINCT customer_id) correctly returns 0.

A final edge case is an empty table. Even if the Store table contains no rows, the query still executes correctly and returns 0 because there are no qualifying customers to count.