LeetCode 2230 - The Users That Are Eligible for Discount

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to identify all users who qualify for a discount based on their purchase history stored in the Purchases table.

Each row in the table contains three pieces of information:

user_id, the identifier of the user
time_stamp, the exact date and time when a purchase occurred
amount, the amount paid during that purchase

A user is considered eligible if there exists at least one purchase that satisfies both of the following conditions:

The purchase happened within the inclusive date interval [startDate, endDate]
The purchase amount is greater than or equal to minAmount

An important detail is how the dates are interpreted. The problem explicitly states that both startDate and endDate should be treated as the start of their respective days. That means:

startDate = 2022-03-08 becomes 2022-03-08 00:00:00
endDate = 2022-03-20 becomes 2022-03-20 00:00:00

This detail is easy to overlook. A purchase made later during the endDate day, such as 2022-03-20 10:00:00, would actually be excluded because the comparison endpoint is exactly midnight.

The expected output is a table containing only the user_id values of eligible users, sorted in ascending order.

Because the problem only asks whether a qualifying purchase exists, we do not need to count purchases or aggregate totals. We simply need to filter rows that satisfy the conditions and return the distinct users associated with those rows.

The table guarantees that (user_id, time_stamp) is unique, which means there are no duplicate purchase records for the same timestamp. This simplifies the logic because we do not need to worry about duplicate rows affecting the result.

Several edge cases are important:

A user may have purchases in the date range but with insufficient amounts
A user may have large purchases outside the allowed date range
A user may have multiple qualifying purchases, but should appear only once in the result
Purchases exactly at startDate 00:00:00 or endDate 00:00:00 are included because the interval is inclusive
Purchases later during endDate are excluded because the end boundary is the start of the day

Approaches

Brute Force Approach

The brute force approach would examine every purchase row one by one and manually evaluate the two required conditions.

For each purchase:

Check whether the timestamp lies within the inclusive interval
Check whether the amount is at least minAmount
If both conditions are true, add the user_id to a result set

After processing all rows, we would sort the unique user IDs and return them.

This approach is correct because every purchase is explicitly checked against the eligibility rules. If any purchase satisfies the conditions, the associated user is included.

Although this method is straightforward, it can become inefficient on large datasets because every row must be scanned manually. In SQL terms, this corresponds to a full table scan without leveraging optimized filtering and projection.

Optimal Approach

The key observation is that the problem is fundamentally a filtering operation.

We do not need complex joins, grouping logic, or aggregation. We simply need to:

Filter rows by timestamp range
Filter rows by minimum amount
Return distinct user IDs

SQL databases are highly optimized for this kind of operation. By applying filtering directly in the WHERE clause and using DISTINCT, the database engine can efficiently produce the result.

The optimal solution therefore consists of a single SQL query using:

WHERE for filtering
DISTINCT for uniqueness
ORDER BY for sorted output

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(k)	Scans all rows manually and stores qualifying users
Optimal	O(n)	O(k)	Uses SQL filtering and DISTINCT directly in the database engine

Here:

n is the number of purchase records
k is the number of qualifying users

Algorithm Walkthrough

Start by reading all rows from the Purchases table.
For each row, check whether the time_stamp falls within the inclusive interval:

time_stamp >= startDate
AND
time_stamp <= endDate

Because both dates are interpreted as the start of the day, the comparison is performed directly against midnight timestamps. 3. Check whether the purchase amount satisfies:

amount >= minAmount

This ensures the purchase is large enough to qualify for the discount. 4. If both conditions are true, keep the corresponding user_id. 5. Since a user may have multiple qualifying purchases, use DISTINCT to remove duplicates. 6. Sort the final result by user_id in ascending order using ORDER BY.

Why it works

The algorithm works because it directly implements the definition of eligibility given in the problem statement. Every purchase is evaluated against the required conditions, and any user with at least one qualifying purchase is included. Using DISTINCT guarantees that each user appears only once, even if multiple purchases qualify.

Python Solution

# Write your MySQL query statement below
SELECT DISTINCT user_id
FROM Purchases
WHERE time_stamp >= startDate
  AND time_stamp <= endDate
  AND amount >= minAmount
ORDER BY user_id;

The query begins by selecting user_id from the Purchases table. Since a user may qualify multiple times, DISTINCT is used to eliminate duplicates.

The WHERE clause applies the two required filters:

The timestamp must lie inside the allowed interval
The amount must be at least minAmount

Finally, ORDER BY user_id ensures the output is sorted as required by the problem statement.

Even though this section is labeled "Python Solution", LeetCode database problems expect SQL queries rather than Python code. The provided query is fully submittable.

Go Solution

// Write your MySQL query statement below
SELECT DISTINCT user_id
FROM Purchases
WHERE time_stamp >= startDate
  AND time_stamp <= endDate
  AND amount >= minAmount
ORDER BY user_id;

Database problems on LeetCode are language independent because the solution is written in SQL. Therefore, the same SQL query applies regardless of whether the selected language is Python, Go, Java, or another supported language.

Unlike traditional algorithm problems, there are no Go-specific implementation concerns such as slices, maps, integer overflow, or nil handling because the logic is entirely expressed through SQL operations.

Worked Examples

Example 1

Input:

Purchases:
+---------+---------------------+--------+
| 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    |
+---------+---------------------+--------+

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

The effective interval becomes:

[2022-03-08 00:00:00, 2022-03-20 00:00:00]

Now evaluate each row.

user_id	time_stamp	amount	In Date Range?	Amount Valid?	Qualifies?
1	2022-04-20 09:03:00	4416	No	Yes	No
2	2022-03-19 19:24:02	678	Yes	No	No
3	2022-03-18 12:03:09	4523	Yes	Yes	Yes
3	2022-03-30 09:43:42	626	No	No	No

Only user 3 has a purchase satisfying both conditions.

Output:

+---------+
| user_id |
+---------+
| 3       |
+---------+

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each purchase row is examined once
Space	O(k)	Stores qualifying distinct users

The query performs a scan over the purchase records while applying filters. The database engine may optimize execution using indexes if available, but in the general case the operation is linear in the number of rows. The extra space comes from maintaining the distinct set of qualifying user IDs.

Test Cases

# Example from problem statement
# Only user 3 satisfies both conditions
assert solution == [3]

# Purchase exactly at start boundary
# Boundary timestamps should be included
assert solution == [1]

# Purchase exactly at end boundary
# Inclusive end boundary at 00:00:00
assert solution == [2]

# Purchase later during endDate
# Should be excluded because endDate is midnight
assert solution == []

# User has multiple qualifying purchases
# DISTINCT should remove duplicates
assert solution == [5]

# User has valid amount but invalid date
assert solution == []

# User has valid date but insufficient amount
assert solution == []

# Multiple users qualify
assert solution == [1, 2, 4]

# Empty result case
assert solution == []

# Single purchase satisfies all conditions
assert solution == [10]

Test Case Summary

Test	Why
Problem statement example	Validates standard filtering behavior
Purchase at start boundary	Confirms inclusive lower bound
Purchase at end boundary	Confirms inclusive upper bound
Purchase later on endDate	Verifies midnight interpretation
Multiple qualifying purchases	Ensures DISTINCT removes duplicates
Valid amount but wrong date	Validates date filtering
Valid date but low amount	Validates amount filtering
Multiple qualifying users	Confirms sorting and multiple outputs
Empty result	Ensures no invalid users returned
Single valid purchase	Tests minimal qualifying case

Edge Cases

Purchase Exactly at the End Boundary

One subtle edge case involves purchases occurring exactly at endDate 00:00:00.

For example:

time_stamp = 2022-03-20 00:00:00

This purchase must be included because the interval is inclusive. However, a purchase later that same day:

2022-03-20 08:00:00

must be excluded. Many incorrect solutions accidentally treat endDate as the entire day rather than the start of the day. The implementation handles this correctly by performing direct timestamp comparisons.

Multiple Qualifying Purchases for the Same User

A user may have several purchases satisfying the conditions. Without DISTINCT, the result could contain duplicate user IDs.

For example:

user_id = 5

might appear three times in the filtered rows. Using DISTINCT guarantees the final output contains only one occurrence of each eligible user.

No Users Qualify

It is possible that no purchase satisfies both conditions simultaneously.

For example:

all purchases may have insufficient amounts
all timestamps may fall outside the interval

The implementation naturally handles this case because the filtered query simply returns an empty result set.

Large Purchase Outside the Allowed Range

A naive implementation might incorrectly prioritize the amount condition and ignore timestamps.

For example:

amount = 100000

does not matter if the purchase occurred outside the valid interval. The query correctly requires both conditions to hold simultaneously using the AND operator.