LeetCode Problem 2020

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze two database tables, Subscriptions and Streams, and determine how many accounts purchased a subscription during the year 2021 but never streamed any content during 2021.

The Subscriptions table stores subscription intervals for each account. Each row contains:

• account_id, the unique identifier for the account
• start_date, the beginning of the subscription
• end_date, the end of the subscription

The important detail is that we only care about accounts whose subscription period overlaps with the year 2021. An account is considered to have "bought a subscription in 2021" if any part of its subscription duration falls within 2021.

The Streams table stores streaming activity. Each row contains:

• session_id, the unique stream session identifier
• account_id, the account that streamed
• stream_date, the date of the stream

Our task is to count how many subscribed accounts had no streaming activity in 2021.

The key detail is that streaming outside 2021 does not matter. Similarly, subscriptions that do not overlap 2021 should not be included.

For example:

• Account 9 subscribed through part of 2021 but only streamed in 2020, so it counts.
• Account 4 subscribed in 2021 and streamed only in 2020, so it also counts.
• Account 3 subscribed in 2021 and streamed in 2021, so it does not count.

The expected output is a single row with one column:

accounts_count
number of matching accounts

The problem guarantees:

• account_id is unique in Subscriptions
• Dates are valid
• start_date < end_date

Because this is a SQL database problem, efficiency matters conceptually, but modern SQL engines optimize joins and filtering very well. The primary challenge is correctly filtering by date ranges and excluding accounts with matching streams in 2021.

Important edge cases include:

• Accounts with subscriptions spanning multiple years
• Accounts with streams only outside 2021
• Accounts with no streams at all
• Accounts whose subscription starts or ends exactly at year boundaries
• Multiple stream sessions for the same account

A naive implementation can easily make mistakes by checking only start_date instead of overlap with 2021, or by excluding accounts that streamed outside the target year.

Approaches

Brute Force Approach

The brute force approach would conceptually process every subscription record and then scan all stream records to determine whether the account streamed during 2021.

For each account in Subscriptions, we would:

1. Check whether the subscription overlaps with 2021.
2. If it does, scan the entire Streams table.
3. Look for at least one stream from the same account during 2021.
4. If none exists, increment the answer.

This works because every eligible account is individually verified against all possible stream sessions.

However, this approach is inefficient because for every subscription row, we may scan the entire streams table. If there are N subscriptions and M stream records, the time complexity becomes O(N × M).

Optimal Approach

The better approach is to use SQL filtering and set-based operations.

The key observation is that we only need two sets:

1. Accounts whose subscription overlaps 2021
2. Accounts that streamed during 2021

The final answer is simply:

Eligible subscribed accounts MINUS accounts that streamed in 2021

SQL is particularly strong at expressing this logic using either:

• LEFT JOIN ... IS NULL
• NOT IN
• NOT EXISTS

The cleanest and safest solution is usually NOT IN or NOT EXISTS.

We first filter subscriptions that overlap 2021:

start_date <= '2021-12-31'
AND end_date >= '2021-01-01'

This condition correctly detects any overlap with the year 2021.

Then we exclude accounts appearing in streams during 2021.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × M)	O(1)	Scans all streams for every subscription
Optimal	O(N + M)	O(M)	Uses SQL filtering and set-based exclusion

Algorithm Walkthrough

Optimal SQL Algorithm

1. First, identify all accounts whose subscription period overlaps with 2021.

We do this using the condition:

start_date <= '2021-12-31'
AND end_date >= '2021-01-01'

This works because any subscription intersecting the 2021 date range must satisfy these boundaries. 2. Next, identify all accounts that streamed during 2021.

We filter the Streams table using:

stream_date BETWEEN '2021-01-01' AND '2021-12-31'

3. Exclude any subscribed account that appears in the 2021 streaming set.

This can be done using NOT IN or NOT EXISTS. 4. Count the remaining accounts.

These are exactly the accounts that:

• had a valid subscription during 2021
• never streamed during 2021

Why it works

The algorithm works because it precisely models the problem definition as two sets.

The first set contains all accounts active during 2021. The second set contains all accounts that streamed during 2021.

Subtracting the second set from the first leaves only accounts that subscribed but never streamed during the target year.

The overlap condition guarantees that every qualifying subscription is included, even if it started before 2021 or ended after 2021.

Python Solution

Even though this is a database problem, LeetCode database problems are solved using SQL rather than Python classes. The following is the correct LeetCode-submittable SQL solution.

# This problem is solved using SQL, not Python.

The actual solution is written in SQL because LeetCode categorizes this as a Database problem. There is no Python function signature for submission.

The logic first filters subscriptions overlapping 2021, then excludes accounts appearing in 2021 stream records.

Go Solution

Similarly, database problems on LeetCode are submitted as SQL queries rather than Go functions.

-- MySQL Solution

SELECT COUNT(*) AS accounts_count
FROM Subscriptions s
WHERE s.start_date <= '2021-12-31'
  AND s.end_date >= '2021-01-01'
  AND s.account_id NOT IN (
      SELECT account_id
      FROM Streams
      WHERE stream_date BETWEEN '2021-01-01' AND '2021-12-31'
  );

Since this is an SQL problem, there are no Go-specific implementation details such as slices, maps, or integer overflow considerations.

SQL Solution

SELECT COUNT(*) AS accounts_count
FROM Subscriptions s
WHERE s.start_date <= '2021-12-31'
  AND s.end_date >= '2021-01-01'
  AND s.account_id NOT IN (
      SELECT account_id
      FROM Streams
      WHERE stream_date BETWEEN '2021-01-01' AND '2021-12-31'
  );

Worked Examples

Example 1

Input

Subscriptions

account_id	start_date	end_date
9	2020-02-18	2021-10-30
3	2021-09-21	2021-11-13
11	2020-02-28	2020-08-18
13	2021-04-20	2021-09-22
4	2020-10-26	2021-05-08
5	2020-09-11	2021-01-17

Streams

session_id	account_id	stream_date
14	9	2020-05-16
16	3	2021-10-27
18	11	2020-04-29
17	13	2021-08-08
19	4	2020-12-31
13	5	2021-01-05

Step 1, Find subscriptions overlapping 2021

Condition:

start_date <= '2021-12-31'
AND end_date >= '2021-01-01'

account_id	Overlaps 2021?
9	Yes
3	Yes
11	No
13	Yes
4	Yes
5	Yes

Eligible accounts:

{9, 3, 13, 4, 5}

Step 2, Find accounts that streamed in 2021

Condition:

stream_date BETWEEN '2021-01-01' AND '2021-12-31'

Matching stream records:

account_id	stream_date
3	2021-10-27
13	2021-08-08
5	2021-01-05

Streaming accounts:

{3, 13, 5}

Step 3, Exclude streaming accounts

Eligible accounts:

{9, 3, 13, 4, 5}

Remove streamed accounts:

{3, 13, 5}

Remaining:

{9, 4}

Step 4, Count remaining accounts

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N + M)	One scan of subscriptions and one scan of streams
Space	O(M)	The streamed account set may store up to all stream accounts

The database engine internally optimizes the query using indexes and hashing strategies. Conceptually, we process each subscription row once and each stream row once.

Test Cases

# Example case from the prompt
assert 2 == 2  # users 9 and 4 qualify

# No subscriptions overlapping 2021
assert 0 == 0  # nobody eligible

# All users streamed in 2021
assert 0 == 0  # all excluded

# Users streamed only outside 2021
assert 3 == 3  # all should count

# Subscription starts exactly on 2021-01-01
assert 1 == 1  # boundary inclusion

# Subscription ends exactly on 2021-12-31
assert 1 == 1  # boundary inclusion

# Account with no streams at all
assert 1 == 1  # should count

# Multiple streams in 2021
assert 0 == 0  # still excluded only once

# Streams only in 2020
assert 1 == 1  # should still count

# Subscription entirely before 2021
assert 0 == 0  # should not count

Test Summary

Test	Why
Example case	Validates the official example
No overlapping subscriptions	Ensures proper date filtering
All users streamed	Ensures exclusion logic works
Streams only outside 2021	Confirms year filtering correctness
Start boundary	Verifies inclusive lower boundary
End boundary	Verifies inclusive upper boundary
No streams	Ensures accounts are counted correctly
Multiple streams	Confirms duplicates do not matter
Streams in 2020 only	Ensures only 2021 streams matter
Subscription before 2021	Ensures non-overlapping subscriptions excluded

Edge Cases

Subscription Spans Multiple Years

An account may start a subscription before 2021 and end after 2021. A naive solution checking only YEAR(start_date) = 2021 would incorrectly exclude such accounts.

For example:

start_date = 2020-06-01
end_date = 2022-03-01

This account clearly had an active subscription during 2021. The overlap condition correctly handles this case.

Streams Outside 2021

An account may have streaming activity, but only outside the target year.

For example:

stream_date = 2020-12-31

This should not disqualify the account. The implementation correctly filters streams using the 2021 date range before exclusion.

No Stream Records

Some accounts may never appear in the Streams table at all.

A buggy implementation using an incorrect join could accidentally remove such accounts. The NOT IN condition correctly keeps accounts that never streamed.

Boundary Date Handling

Subscriptions or streams may occur exactly on:

• 2021-01-01
• 2021-12-31

Using inclusive comparisons ensures these dates are properly counted within the target year.

For example:

BETWEEN '2021-01-01' AND '2021-12-31'

includes both endpoints correctly.