Skip to main content
Talentd

Ad-Free Sessions - Solution & Explanation

EasyPremiumFree on FleetCodeDatabase4 min readAsked at: Amazon
Practice this problem

Problem Statement

Table: Playback

+-------------+------+
| Column Name | Type |
+-------------+------+
| session_id  | int  |
| customer_id | int  |
| start_time  | int  |
| end_time    | int  |
+-------------+------+
session_id is the column with unique values for this table.
customer_id is the ID of the customer watching this session.
The session runs during the inclusive interval between start_time and end_time.
It is guaranteed that start_time <= end_time and that two sessions for the same customer do not intersect.

 

Table: Ads

+-------------+------+
| Column Name | Type |
+-------------+------+
| ad_id       | int  |
| customer_id | int  |
| timestamp   | int  |
+-------------+------+
ad_id is the column with unique values for this table.
customer_id is the ID of the customer viewing this ad.
timestamp is the moment of time at which the ad was shown.

 

Write a solution to report all the sessions that did not get shown any ads.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Playback table:
+------------+-------------+------------+----------+
| session_id | customer_id | start_time | end_time |
+------------+-------------+------------+----------+
| 1          | 1           | 1          | 5        |
| 2          | 1           | 15         | 23       |
| 3          | 2           | 10         | 12       |
| 4          | 2           | 17         | 28       |
| 5          | 2           | 2          | 8        |
+------------+-------------+------------+----------+
Ads table:
+-------+-------------+-----------+
| ad_id | customer_id | timestamp |
+-------+-------------+-----------+
| 1     | 1           | 5         |
| 2     | 2           | 17        |
| 3     | 2           | 20        |
+-------+-------------+-----------+
Output: 
+------------+
| session_id |
+------------+
| 2          |
| 3          |
| 5          |
+------------+
Explanation: 
The ad with ID 1 was shown to user 1 at time 5 while they were in session 1.
The ad with ID 2 was shown to user 2 at time 17 while they were in session 4.
The ad with ID 3 was shown to user 2 at time 20 while they were in session 4.
We can see that sessions 1 and 4 had at least one ad. Sessions 2, 3, and 5 did not have any ads, so we return them.

Approach Overview

Problem Overview: You’re given playback sessions and ad events for each customer. A session is considered ad‑free if no ad timestamp falls between the session’s start_time and end_time for the same customer. The task is to return the session_id of all sessions where this condition holds.

Approach 1: NOT EXISTS Anti-Subquery (O(P * A) without indexes, ~O(P log A) with indexes)

Scan each session in the Playback table and check whether an ad exists for the same customer_id within the session time range. A correlated subquery with NOT EXISTS filters out sessions that contain at least one matching ad. The key idea is that the database stops searching as soon as it finds a matching row, making this efficient with proper indexes on (customer_id, timestamp). This pattern is a classic anti-join used frequently in SQL and database interview problems.

Approach 2: LEFT JOIN with NULL Filter (O(P * A) without indexes, ~O(P log A) with indexes)

Another way is performing a LEFT JOIN between Playback and Ads on matching customer_id and a timestamp range condition: Ads.timestamp BETWEEN Playback.start_time AND Playback.end_time. If a session has no matching ad rows, the joined columns from Ads remain NULL. Filtering rows where the ad column is NULL keeps only ad‑free sessions. This approach expresses the same anti-join logic but through a join operation, which some developers find easier to read when working with SQL joins.

Recommended for interviews: The NOT EXISTS solution is typically preferred. It directly models the requirement: return sessions where no ad exists in the time range. Interviewers often expect this form because it clearly communicates the anti-join logic and avoids accidental duplicates that can appear with joins if grouping is not handled carefully.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
NOT EXISTS Anti-SubqueryO(P * A) worst case, ~O(P log A) with indexO(1)Best general solution. Clear anti-join logic and efficient with indexes.
LEFT JOIN + NULL FilterO(P * A) worst case, ~O(P log A) with indexO(1)Useful when you prefer explicit joins or when combining with other joined tables.

Video Solution

LeetCode 1809 "Ad-Free Sessions" Amazon Interview SQL Question with Detailed Explanation • Everyday Data Science • 1,998 views views

Frequently Asked Questions

Is Ad-Free Sessions easy or hard?
Ad-Free Sessions is classified as an Easy database problem. The main challenge is recognizing the anti-join pattern and correctly filtering timestamps within the session range using NOT EXISTS or a LEFT JOIN with a NULL check.
Ad-Free Sessions Python/Java solution
Unlike algorithm problems solved in Python or Java, this question is solved directly in SQL. The typical MySQL solution selects session IDs from Playback where NOT EXISTS a matching ad record with the same customer_id and a timestamp between the session start and end times.
How to solve Ad-Free Sessions in O(n)?
Pure O(n) is not typical for SQL joins across two tables, but indexed lookups make the query close to linear in practice. Create an index on Ads(customer_id, timestamp) and use a NOT EXISTS subquery checking timestamps between start_time and end_time. Each session then performs a fast indexed range check.
What is the best approach for Ad-Free Sessions?
The NOT EXISTS anti-subquery approach is the most reliable solution. It checks each playback session and filters out sessions where an ad timestamp exists within the session time range for the same customer. With indexes on (customer_id, timestamp), the query runs efficiently and clearly expresses the problem logic.
Is Ad-Free Sessions asked at Google/Amazon/Meta?
This style of SQL problem appears frequently in data and backend interview rounds at companies like Amazon, Meta, and Google. The pattern tests your understanding of anti-joins, time-range filtering, and efficient querying with NOT EXISTS or LEFT JOIN.
What data structure is used in Ad-Free Sessions?
The problem relies on relational database tables and SQL query operations rather than traditional data structures. Conceptually it uses joins, anti-joins, and range filtering on timestamps, which are core database query techniques.
What is the time complexity of Ad-Free Sessions?
The logical worst-case complexity is O(P * A), where P is the number of playback sessions and A is the number of ad records. With proper indexing on customer_id and timestamp, the database engine can perform range lookups, reducing the practical cost to roughly O(P log A). Space complexity is O(1).

Ready to solve this problem?

Practice Ad-Free Sessions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary