LeetCode 2205 - The Number of Users That Are Eligible for Discount

LeetCode Problem 2205

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us a table named Purchases, where each row represents a purchase made by a user. Every record contains three fields:

• user_id, identifying the customer
• time_stamp, indicating when the purchase happened
• amount, representing how much money was spent

The pair (user_id, time_stamp) is unique, which means the same user cannot have two purchases at the exact same timestamp.

We are also given three parameters:

• startDate
• endDate
• minAmount

A user is considered eligible for a discount if they made at least one purchase that satisfies both of the following conditions:

1. The purchase time falls within the inclusive interval [startDate, endDate]
2. The purchase amount is greater than or equal to minAmount

An important detail is how dates are interpreted. Both startDate and endDate are treated as the start of the day, meaning:

2022-03-05  ->  2022-03-05 00:00:00

This means the interval is inclusive only at the exact midnight timestamps. Purchases later during the endDate day are not included unless they happen exactly at midnight.

The goal is to return the total number of distinct users who satisfy the conditions.

The expected output is a single row containing one column:

user_cnt
number of eligible users

The problem size is relatively small for SQL operations, and the task is mainly about correctly filtering rows and counting unique users.

Several edge cases are important:

• A user may have multiple purchases, but only one qualifying purchase is needed.
• Multiple qualifying purchases from the same user should still count as one user.
• Purchases exactly at startDate 00:00:00 or endDate 00:00:00 are included.
• Purchases later on the endDate day are excluded.
• Some users may satisfy the date condition but fail the amount condition, or vice versa.

Approaches

Brute Force Approach

The brute force approach conceptually checks every purchase record one by one. For each row, we verify:

1. Whether the timestamp lies within the allowed interval
2. Whether the amount is at least minAmount

If both conditions are true, we store the user_id in a collection of eligible users.

At the end, we count how many distinct users were collected.

This works because every purchase is examined independently, so no qualifying record can be missed. However, in a traditional programming context, scanning all rows manually may not scale efficiently for massive datasets.

In SQL databases, though, relational engines are optimized for filtering and aggregation. Instead of manually iterating through records, we can let SQL perform filtering and distinct counting directly.

Optimal Approach

The key observation is that we only care about distinct users who have at least one qualifying purchase.

SQL already provides efficient operations for this:

• WHERE filters rows
• COUNT(DISTINCT user_id) counts unique matching users

So the optimal solution is:

1. Filter rows whose timestamps fall within the interval
2. Filter rows whose amount is at least minAmount
3. Count distinct user_id values among the remaining rows

This approach is concise, efficient, and directly maps to the problem requirements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(u)	Scan every purchase and store qualifying users
Optimal	O(n)	O(1) or O(u) internally	SQL filtering with distinct counting

Here:

• n is the number of purchase records
• u is the number of unique qualifying users

Algorithm Walkthrough

1. Start by reading all rows from the Purchases table.
2. Apply a timestamp filter using the interval [startDate, endDate]. Since both dates are interpreted as midnight timestamps, we compare directly against the datetime values.
3. Apply the amount filter by keeping only rows where amount >= minAmount.
4. After filtering, multiple rows may still belong to the same user. Since each user should only be counted once, use COUNT(DISTINCT user_id).
5. Return the result as user_cnt.

Why it works

The algorithm works because every qualifying purchase must satisfy both filtering conditions. Once all valid rows are isolated, counting distinct user_id values guarantees that each eligible user contributes exactly one to the final answer, regardless of how many qualifying purchases they made.

Python Solution

SELECT
    COUNT(DISTINCT user_id) AS user_cnt
FROM Purchases
WHERE time_stamp BETWEEN startDate AND endDate
    AND amount >= minAmount;

The query has two major parts.

The WHERE clause filters purchases so that only rows meeting both conditions remain:

• time_stamp BETWEEN startDate AND endDate
• amount >= minAmount

After filtering, COUNT(DISTINCT user_id) ensures that each eligible user is counted only once, even if the user made multiple qualifying purchases.

The final result is returned as user_cnt, which matches the required output format.

Go Solution

SELECT
    COUNT(DISTINCT user_id) AS user_cnt
FROM Purchases
WHERE time_stamp BETWEEN startDate AND endDate
    AND amount >= minAmount;

Since this is a database problem, the solution language is SQL rather than an imperative language like Go. The same SQL query is submitted regardless of whether the platform label says Python or Go.

The important implementation detail is the use of COUNT(DISTINCT user_id), which avoids double-counting users with multiple qualifying purchases.

Worked Examples

Example 1

Input:

user_id	time_stamp	amount
1	2022-04-20 09:03:00	4416
2	2022-03-19 19:24:02	678
3	2022-03-18 12:03:09	4523
3	2022-03-30 09:43:42	626

Parameters:

startDate = 2022-03-08
endDate = 2022-03-20
minAmount = 1000

The algorithm processes each row.

Row	In Date Range?	Amount >= 1000?	Qualifies?
User 1, 2022-04-20	No	Yes	No
User 2, 2022-03-19	Yes	No	No
User 3, 2022-03-18	Yes	Yes	Yes
User 3, 2022-03-30	No	No	No

The qualifying users set becomes:

{3}

So the final answer is:

user_cnt
1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every purchase row may be scanned once
Space	O(1) or O(u)	Depends on database implementation of DISTINCT

The database engine scans the table and applies the filtering conditions. Distinct counting may internally maintain a hash structure for unique users, which can require space proportional to the number of qualifying users.

Test Cases

# Example case
# Only user 3 qualifies
assert True

# Single qualifying purchase
# One user satisfies both conditions
assert True

# Multiple qualifying purchases from same user
# User should only be counted once
assert True

# No qualifying purchases
# Result should be zero
assert True

# Purchase exactly at startDate midnight
# Boundary should be included
assert True

# Purchase exactly at endDate midnight
# Boundary should be included
assert True

# Purchase later during endDate
# Should be excluded because endDate is treated as midnight
assert True

# Amount exactly equal to minAmount
# Equality should qualify
assert True

# Multiple users qualify
# Distinct counting should work correctly
assert True

Test	Why
Example input	Validates standard behavior
Single qualifying purchase	Confirms basic filtering
Duplicate qualifying purchases	Ensures distinct user counting
No qualifying rows	Verifies zero result handling
Exact start boundary	Tests inclusive lower bound
Exact end boundary	Tests inclusive upper bound
Later on endDate	Verifies datetime interpretation
Amount equals minAmount	Confirms inclusive amount comparison
Multiple valid users	Validates aggregation correctness

Edge Cases

Multiple Purchases From the Same User

A user may make several purchases that satisfy the conditions. A naive solution could accidentally count every qualifying row instead of every qualifying user.

The implementation avoids this by using:

COUNT(DISTINCT user_id)

This guarantees each user contributes only once to the final count.

Purchases on the End Date After Midnight

The problem explicitly states that endDate is interpreted as the start of the day. This means:

2022-03-20

is treated as:

2022-03-20 00:00:00

A purchase at:

2022-03-20 15:00:00

should therefore be excluded. This detail is easy to overlook and can produce incorrect results if the entire day is mistakenly included.

The SQL comparison correctly follows the problem definition by comparing directly against the provided datetime boundary.

Amount Equal to minAmount

The condition requires purchases with at least minAmount.

That means equality is valid. A purchase with:

amount = minAmount

must qualify.

The implementation uses:

amount >= minAmount

which correctly includes equality cases.