User Activities within Time Bounds - Solution & Explanation

HardPremiumFree on FleetCodeDatabase5 min read

Problem Statement

Table: Sessions

+---------------+----------+
| Column Name   | Type     |
+---------------+----------+
| user_id       | int      |
| session_start | datetime |
| session_end   | datetime |
| session_id    | int      |
| session_type  | enum     |
+---------------+----------+
session_id is column of unique values for this table.
session_type is an ENUM (category) type of (Viewer, Streamer).
This table contains user id, session start, session end, session id and session type.

Write a solution to find the the users who have had at least two session of the same type (either 'Viewer' or 'Streamer') with a maximum gap of 12 hours between sessions.

Return the result table ordered by user_id in ascending order.

The result format is in the following example.

Example:

Input: 
Sessions table:
+---------+---------------------+---------------------+------------+--------------+
| user_id | session_start       | session_end         | session_id | session_type | 
+---------+---------------------+---------------------+------------+--------------+
| 101     | 2023-11-01 08:00:00 | 2023-11-01 09:00:00 | 1          | Viewer       |  
| 101     | 2023-11-01 10:00:00 | 2023-11-01 11:00:00 | 2          | Streamer     |   
| 102     | 2023-11-01 13:00:00 | 2023-11-01 14:00:00 | 3          | Viewer       | 
| 102     | 2023-11-01 15:00:00 | 2023-11-01 16:00:00 | 4          | Viewer       | 
| 101     | 2023-11-02 09:00:00 | 2023-11-02 10:00:00 | 5          | Viewer       | 
| 102     | 2023-11-02 12:00:00 | 2023-11-02 13:00:00 | 6          | Streamer     | 
| 101     | 2023-11-02 13:00:00 | 2023-11-02 14:00:00 | 7          | Streamer     | 
| 102     | 2023-11-02 16:00:00 | 2023-11-02 17:00:00 | 8          | Viewer       | 
| 103     | 2023-11-01 08:00:00 | 2023-11-01 09:00:00 | 9          | Viewer       | 
| 103     | 2023-11-02 20:00:00 | 2023-11-02 23:00:00 | 10         | Viewer       | 
| 103     | 2023-11-03 09:00:00 | 2023-11-03 10:00:00 | 11         | Viewer       | 
+---------+---------------------+---------------------+------------+--------------+
Output: 
+---------+
| user_id |
+---------+
| 102     |
| 103     |
+---------+
Explanation:
- User ID 101 will not be included in the final output as they do not have any two sessions of the same session type.
- User ID 102 will be included in the final output as they had two viewer sessions with session IDs 3 and 4, respectively, and the time gap between them was less than 12 hours.
- User ID 103 participated in two viewer sessions with a gap of less than 12 hours between them, identified by session IDs 10 and 11. Therefore, user 103 will be included in the final output.
Output table is ordered by user_id in increasing order.

Approach Overview

Problem Overview: You are given a table of user activity records with timestamps. The goal is to detect activities that occur within specific time bounds for the same user. Instead of checking every pair of records, the challenge is to efficiently compare nearby activities in chronological order.

Approach 1: Self Join with Time Difference (O(n^2) time, O(1) extra space)

A straightforward method joins the activity table with itself on user_id. For each pair of rows belonging to the same user, compute the time difference using a SQL time function such as TIMESTAMPDIFF(). Then filter rows where the difference falls within the required bounds. This works but scales poorly because each row may be compared with many others. On large datasets, the quadratic comparison cost becomes expensive.

Approach 2: Window Function + Time Function (O(n log n) time, O(n) space)

A more scalable strategy orders each user's activities by timestamp and compares adjacent records using a window function. Use LAG() or LEAD() with PARTITION BY user_id ORDER BY activity_time to access the previous or next event for the same user. Then compute the difference between timestamps with a time function such as TIMESTAMPDIFF() or equivalent logic in Python. Because each row is only compared with its immediate neighbor, the number of comparisons drops dramatically. The dominant cost is sorting events by user and time, which takes O(n log n).

This pattern is common in database analytics. Window functions let you analyze sequences of events without expensive joins. The database scans the ordered partition once, making the query efficient even with millions of records.

Conceptually, the algorithm works like this: partition activities by user, sort by timestamp, fetch the previous activity with LAG(), compute the time difference, and filter rows where the difference lies inside the allowed bounds. Many production analytics pipelines use this same design for session detection, anomaly detection, and activity clustering.

Recommended for interviews: The window function approach is what interviewers expect. The self-join approach shows you understand relational comparisons, but it does not scale well. Using LAG() demonstrates familiarity with analytical SQL and efficient event-sequence processing. Problems like this frequently appear in database interview rounds that test knowledge of window functions, SQL joins, and time functions.

Solution

First, we use the LAG window function to find the end time of the previous session of the same type for each user, denoted as prev_session_end. Then we use the TIMESTAMPDIFF function to calculate the time difference between the start time of the current session and the end time of the previous session. If the time difference is less than or equal to 12 hours, then this user meets the requirements of the problem.

Code

MySQL Python

MySQL

Python

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Self Join with Time Difference	O(n^2)	O(1)	Small datasets or quick prototype queries
Window Function + Time Function	O(n log n)	O(n)	Large datasets where events must be compared sequentially per user

Video Solution

Leetcode HARD 3060 - Self Joins Vs Window Functions in SQL Explained | Everyday Data Science • Everyday Data Science • 513 views views

Frequently Asked Questions

Is User Activities within Time Bounds easy or hard?

User Activities within Time Bounds is considered a hard database problem. It requires knowledge of analytical SQL features such as window functions, careful ordering of event data, and correct handling of timestamp differences.

User Activities within Time Bounds Python/Java solution

In Python, you can replicate the SQL idea by grouping activities by user, sorting them by timestamp, and iterating through adjacent pairs to compute time differences. Java implementations follow the same pattern using collections and sorting before scanning the sequence.

How to solve User Activities within Time Bounds in O(n)?

Pure O(n) is difficult in SQL because rows must usually be ordered by time first. After sorting, a window function like LAG() lets you compare each activity with its previous event in constant time per row. This effectively becomes O(n log n) overall due to the sorting step.

What is the best approach for User Activities within Time Bounds?

The most efficient solution uses SQL window functions such as LAG() or LEAD() combined with time difference functions. Partition activities by user, order them by timestamp, and compute the difference between consecutive rows. This reduces comparisons and runs in roughly O(n log n) time due to sorting.

Is User Activities within Time Bounds asked at Google/Amazon/Meta?

Database problems involving event sequences and time windows are common in data engineering and analytics interviews at companies like Google, Amazon, and Meta. Candidates are often expected to use window functions to analyze ordered user events efficiently.

What data structure is used in User Activities within Time Bounds?

The core concept relies on ordered partitions created by SQL window functions. Internally the database sorts rows by user and timestamp, then exposes neighboring rows through functions like LAG() or LEAD() for efficient comparisons.

What is the time complexity of User Activities within Time Bounds?

The optimal solution runs in O(n log n) time. The database first sorts activities by user and timestamp, then scans each partition once using a window function to compute time differences. Space complexity is O(n) for intermediate query processing.

Ready to solve this problem?

Practice User Activities within Time Bounds with our built-in code editor and test cases.

Practice on FleetCode

Combine Two Tables

Second Highest Salary

Problem Info

DifficultyHard

Acceptance40.6%

Approaches1

Reading time5 min

Practice this problem

Open in Editor