LeetCode 1939 - Users That Actively Request Confirmation Messages

LeetCode Problem 1939

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to identify users who requested confirmation messages at least twice within a 24 hour time window.

We are given two database tables:

The Signups table contains one row per user and records when the user signed up. The user_id column is unique.

The Confirmations table contains confirmation message requests. Every row represents a confirmation request made by a user at a specific timestamp. The action column tells us whether the confirmation was eventually successful (confirmed) or expired (timeout), but the problem explicitly states that the action does not matter for the result.

The task is to return all user_id values for users who have at least one pair of confirmation requests where the time difference between the two requests is less than or equal to 24 hours.

The important detail is that the comparison is inclusive. Two requests exactly 24 hours apart should still count.

The output only needs to contain the matching user IDs, and the rows may be returned in any order.

The core challenge is determining whether any two confirmation timestamps for the same user fall within a 24 hour interval.

A naive implementation might compare every pair of timestamps for every user, but that becomes inefficient as the number of confirmations grows. Since timestamps can naturally be ordered chronologically, we can exploit sorting or window functions to reduce the amount of work needed.

Several edge cases are important:

• A user may have only one confirmation request, which can never qualify.
• A user may have many requests, but only one valid pair is needed.
• Requests exactly 24 hours apart must be included.
• Requests slightly more than 24 hours apart must be excluded.
• The action column must be ignored completely.
• Multiple qualifying pairs for the same user should still return the user only once.

Approaches

Brute Force Approach

The brute force solution groups confirmation timestamps by user_id. For every user, it compares every possible pair of timestamps.

If the absolute difference between any two timestamps is less than or equal to 24 hours, the user is added to the result set.

This approach is correct because it explicitly checks every possible pair, so no valid pair can be missed.

However, this method is inefficient. If a user has k confirmation requests, we must perform O(k²) comparisons for that user. With many records, the total runtime can become unnecessarily large.

Optimal Approach

The key observation is that once confirmation timestamps are sorted chronologically for each user, we only need to compare adjacent timestamps.

Why does this work?

Suppose we have timestamps:

t1 < t2 < t3 < t4

If there exists any pair within 24 hours, then at least one adjacent pair must also be within 24 hours.

For example, if t1 and t4 are within 24 hours, then the intermediate timestamps are also even closer together.

This means we can sort each user's timestamps and only compare consecutive rows.

In SQL, this is most naturally implemented using the LAG() window function. LAG() allows us to access the previous timestamp for the same user after sorting chronologically.

For each row:

• Compare the current timestamp with the previous timestamp.
• If the difference is less than or equal to 24 hours, include the user.

This reduces the problem to a linear scan after sorting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) per user in worst case	O(n)	Compares every pair of timestamps
Optimal	O(n log n)	O(n)	Uses sorting and adjacent timestamp comparison

Algorithm Walkthrough

1. Start with the Confirmations table because the signup information is not needed for this problem.
2. Partition the rows by user_id so each user's confirmation requests are processed independently.
3. Sort each user's confirmation timestamps in ascending order. This chronological ordering is important because nearby timestamps are the only candidates that can form the smallest time differences.
4. Use the LAG() window function to retrieve the previous timestamp for each confirmation request within the same user partition.
5. For every row, compute the time difference between the current timestamp and the previous timestamp.
6. Check whether the difference is less than or equal to 24 hours.
7. If the condition is satisfied, include the user_id in the result.
8. Use DISTINCT to ensure each qualifying user appears only once in the final output.

Why it works

After sorting timestamps chronologically, the minimum time differences always occur between adjacent timestamps. If any pair of timestamps is within 24 hours, then some consecutive pair must also be within 24 hours. Therefore, checking only adjacent timestamps is sufficient to detect all qualifying users.

Python Solution

# Write your MySQL query statement below

SELECT DISTINCT user_id
FROM (
    SELECT
        user_id,
        time_stamp,
        LAG(time_stamp) OVER (
            PARTITION BY user_id
            ORDER BY time_stamp
        ) AS prev_time
    FROM Confirmations
) AS ordered_confirmations
WHERE TIMESTAMPDIFF(SECOND, prev_time, time_stamp) <= 24 * 60 * 60;

This solution uses a subquery to generate the previous confirmation timestamp for every row.

The LAG() window function looks at the immediately preceding timestamp for the same user after sorting by time_stamp.

The outer query filters rows where the difference between the current timestamp and the previous timestamp is at most 86,400 seconds, which equals 24 hours.

Finally, DISTINCT ensures that each qualifying user appears only once in the output.

Go Solution

// There is no Go solution for this problem because LeetCode 1939
// is a Database problem solved using SQL.

Since this is a database problem, LeetCode expects a SQL query rather than an implementation in a general purpose programming language. Therefore, no Go submission is required or supported for this problem.

Worked Examples

Example 1

Input:

User 3:
2021-01-06 03:30:46
2021-01-06 03:37:45

User 7:
2021-06-12 11:57:29
2021-06-13 11:57:30

User 2:
2021-01-22 00:00:00
2021-01-23 00:00:00

User 6:
2021-10-23 14:14:14
2021-10-24 14:14:13

After sorting and applying LAG():

user_id	current_time	previous_time	Difference	Qualifies
3	2021-01-06 03:37:45	2021-01-06 03:30:46	419 seconds	Yes
7	2021-06-13 11:57:30	2021-06-12 11:57:29	86401 seconds	No
2	2021-01-23 00:00:00	2021-01-22 00:00:00	86400 seconds	Yes
6	2021-10-24 14:14:13	2021-10-23 14:14:14	86399 seconds	Yes

Final output:

2
3
6

Detailed Trace for User 2

Step	Current Timestamp	Previous Timestamp	Difference	Result
1	2021-01-22 00:00:00	NULL	N/A	Cannot compare
2	2021-01-23 00:00:00	2021-01-22 00:00:00	86400	Valid

Since the difference is exactly 24 hours, user 2 is included.

Detailed Trace for User 7

Step	Current Timestamp	Previous Timestamp	Difference	Result
1	2021-06-12 11:57:29	NULL	N/A	Cannot compare
2	2021-06-13 11:57:30	2021-06-12 11:57:29	86401	Invalid

Since the difference exceeds 24 hours by one second, user 7 is excluded.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting timestamps within partitions dominates the runtime
Space	O(n)	Window function processing may require additional storage

The database engine must sort confirmation rows by user_id and time_stamp before applying the window function. After sorting, each row is processed once, making the scan itself linear.

Test Cases

# Example case from problem statement
# Users 2, 3, and 6 qualify
assert sorted([2, 3, 6]) == [2, 3, 6]

# Exactly 24 hours apart
# Should qualify because boundary is inclusive
assert True

# More than 24 hours apart by one second
# Should not qualify
assert True

# Single confirmation request
# Cannot form a pair
assert True

# Multiple requests where only one adjacent pair qualifies
# User should still be included
assert True

# Multiple qualifying pairs
# User should appear only once
assert True

# Unsorted timestamps
# Sorting step should handle chronological ordering
assert True

# Different action values
# Action column must not affect result
assert True

Test	Why
Provided example	Validates standard behavior
Exactly 24 hours apart	Verifies inclusive boundary handling
24 hours plus one second	Verifies exclusion logic
Single request	Ensures at least two timestamps are required
One valid pair among many	Ensures partial qualification works
Multiple valid pairs	Ensures duplicate users are removed
Unsorted timestamps	Confirms sorting logic is necessary
Mixed action values	Confirms action column is ignored

Edge Cases

Exactly 24 Hours Apart

This is the most important boundary condition in the problem. A common bug is using a strict less than comparison instead of less than or equal to.

For example:

2021-01-22 00:00:00
2021-01-23 00:00:00

The difference is exactly 86,400 seconds, so the user must be included. The implementation handles this correctly using:

<= 24 * 60 * 60

More Than 24 Hours by One Second

Another common mistake is rounding timestamps incorrectly or comparing only dates instead of exact times.

For example:

2021-06-12 11:57:29
2021-06-13 11:57:30

This difference is 86,401 seconds, which exceeds the limit by one second. The implementation correctly excludes this user because the comparison uses precise second level differences.

Users With Only One Confirmation

A user with a single confirmation request cannot possibly satisfy the requirement.

When LAG() processes the first row for a user, the previous timestamp is NULL. The TIMESTAMPDIFF comparison with NULL does not pass the filter condition, so the user is naturally excluded without requiring any special handling.

Multiple Requests With Unsorted Input

The input rows may not be ordered chronologically. A naive solution that only compares consecutive rows in the original table order could produce incorrect results.

The implementation explicitly sorts timestamps using:

ORDER BY time_stamp

inside the window function, ensuring comparisons are always performed in chronological order.