LeetCode 1809 - Ad-Free Sessions

LeetCode Problem 1809

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem is asking us to identify all playback sessions during which no advertisements were shown. We are given two tables: Playback and Ads. The Playback table lists sessions for each customer, with the start and end times of each session. Each session is guaranteed to be non-overlapping for the same customer. The Ads table lists the ads shown to customers, along with the timestamp when each ad occurred.

Our goal is to return the session_id of all sessions that did not contain any ad timestamps. This requires checking each session against all ads for that customer to see if any ad falls within the session's inclusive [start_time, end_time] interval.

Important constraints are that the sessions for the same customer do not overlap, and start_time ≤ end_time, which simplifies our checks because we do not need to handle intersecting sessions for the same customer. Edge cases include sessions with no ads at all, multiple ads outside session intervals, and multiple ads exactly on the session boundaries.

Approaches

The brute-force approach is to join each session with all ads for that customer and check whether any ad timestamp falls within the session interval. If no ad is found in the interval, the session is ad-free. This works correctly because it exhaustively checks every session against every ad for that customer, but it is inefficient for large datasets because it may result in a large Cartesian product.

The optimal approach leverages a left join between Playback and Ads on customer_id with an additional condition that the timestamp falls within the session interval. Then, we filter for rows where no matching ad exists (NULL after the join). This reduces unnecessary comparisons and allows the database engine to efficiently filter matches using indexes on customer_id and timestamp.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(P * A)	O(1)	Join each session with all ads for the customer and filter manually
Optimal	O(P + A)	O(1)	Use LEFT JOIN with condition and filter NULLs to efficiently get sessions without ads

Algorithm Walkthrough

1. Start by performing a LEFT JOIN between the Playback table and the Ads table on customer_id. This ensures every session is matched with potential ads for the same customer.
2. Add a condition in the join that the ad timestamp falls within the session's [start_time, end_time] interval. This filters only relevant ads for each session.
3. After the join, rows with no matching ads will have NULL values in the ad columns. Filter the result set for NULL values in the ad_id column.
4. Select the session_id of these filtered rows as the final result.

Why it works: By left joining on customer_id and restricting to ad timestamps within session intervals, any session without an ad will have no match in the Ads table, resulting in NULL. Filtering these NULLs guarantees that we capture only ad-free sessions. This approach works because session intervals are non-overlapping per customer, ensuring no ambiguity.

Python Solution

# SQL-based solution in Python using a raw query approach
def ad_free_sessions() -> str:
    return """
    SELECT p.session_id
    FROM Playback p
    LEFT JOIN Ads a
    ON p.customer_id = a.customer_id
       AND a.timestamp BETWEEN p.start_time AND p.end_time
    WHERE a.ad_id IS NULL
    """

Explanation: We select from Playback as the main table and left join Ads on matching customer_id and timestamp within session bounds. Filtering where ad_id IS NULL ensures only sessions without any ad are returned. This directly implements the algorithm steps described.

Go Solution

// Go version using database/sql raw query
package main

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
    "fmt"
)

func AdFreeSessions(db *sql.DB) ([]int, error) {
    query := `
    SELECT p.session_id
    FROM Playback p
    LEFT JOIN Ads a
    ON p.customer_id = a.customer_id
       AND a.timestamp BETWEEN p.start_time AND p.end_time
    WHERE a.ad_id IS NULL
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var result []int
    for rows.Next() {
        var sessionID int
        if err := rows.Scan(&sessionID); err != nil {
            return nil, err
        }
        result = append(result, sessionID)
    }
    return result, nil
}

Explanation: The Go solution executes the same SQL query as the Python solution. Rows with no matching ad produce NULL for ad_id, and scanning these rows into a slice collects all ad-free session IDs.

Worked Examples

Using the example from the problem:

Playback:

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:

ad_id	customer_id	timestamp
1	1	5
2	2	17
3	2	20

Execution:

1. Join session 1 (customer 1, 1-5) with ads → matches ad 1 (timestamp 5) → excluded.
2. Join session 2 (customer 1, 15-23) with ads → no ad in range → included.
3. Join session 3 (customer 2, 10-12) with ads → no ad in range → included.
4. Join session 4 (customer 2, 17-28) → matches ad 2 and 3 → excluded.
5. Join session 5 (customer 2, 2-8) → no ad in range → included.

Result: session_ids 2, 3, 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(P + A)	Database performs an efficient join with filtering rather than Cartesian product
Space	O(1)	Only the result set is materialized, no additional data structures needed

We assume efficient indexes on customer_id and timestamp allow the database to filter the join efficiently, avoiding the quadratic brute-force cost.

Test Cases

# Example test cases
assert ad_free_sessions() == """
SELECT p.session_id
FROM Playback p
LEFT JOIN Ads a
ON p.customer_id = a.customer_id
   AND a.timestamp BETWEEN p.start_time AND p.end_time
WHERE a.ad_id IS NULL
"""  # checks SQL structure correctness

Test	Why
Provided input	Validates correct identification of ad-free sessions
Session with ad at start	Ensures inclusive bounds are handled
Session with ad at end	Ensures inclusive bounds are handled
Customer with no ads	Checks that all sessions for that customer are included
No sessions	Verifies empty result is handled correctly

Edge Cases

1. Session with ad exactly at start_time or end_time: Since the interval is inclusive, these sessions should be counted as having an ad. Our BETWEEN condition handles this correctly.
2. Customer with no ads at all: All sessions for this customer should appear in the result. The left join produces NULL for all ads, so filtering works as intended.
3. Multiple sessions for the same customer: Each session is independent because sessions do not overlap. Ads are matched individually, so no session is incorrectly marked.

This solution correctly handles all these edge cases, ensuring robust and accurate results.