Solution Explanation for LeetCode 2020: Number of Accounts That Did Not Stream

This problem requires finding the number of accounts that subscribed in 2021 but did not have any streaming sessions during that year. We'll use SQL to achieve this.

Approach:

The core idea is to perform a LEFT JOIN between the Subscriptions and Streams tables. A LEFT JOIN ensures that all rows from the left table (Subscriptions) are included in the result, even if there's no matching row in the right table (Streams). We then filter the results to identify accounts meeting the specified criteria.

SQL Query (MySQL):

SELECT COUNT(sub.account_id) AS accounts_count
FROM
    Subscriptions AS sub
    LEFT JOIN Streams USING (account_id)
WHERE
    YEAR(start_date) <= 2021
    AND YEAR(end_date) >= 2021
    AND (YEAR(stream_date) != 2021 OR stream_date IS NULL OR stream_date > end_date);

Explanation:

1. SELECT COUNT(sub.account_id) AS accounts_count: This counts the number of accounts satisfying the conditions and names the column accounts_count. We use sub.account_id to explicitly specify the account_id from the Subscriptions table, which is important in case of ambiguity.

2. FROM Subscriptions AS sub LEFT JOIN Streams USING (account_id): This performs a LEFT JOIN between Subscriptions (aliased as sub) and Streams tables using account_id as the join key. USING (account_id) is a shorthand for ON sub.account_id = Streams.account_id.

3. WHERE YEAR(start_date) <= 2021 AND YEAR(end_date) >= 2021: This filters for accounts that had subscriptions starting on or before 2021 and ending on or after 2021 – meaning they were subscribed at some point in 2021.

4. AND (YEAR(stream_date) != 2021 OR stream_date IS NULL OR stream_date > end_date): This is the crucial condition. It checks for accounts where:

   • YEAR(stream_date) != 2021: The streaming session was not in 2021 (meaning no stream in 2021).
   • stream_date IS NULL: There were no streaming sessions associated with that account (a LEFT JOIN will return NULL for stream_date if no match in Streams table).
   • stream_date > end_date: The streaming session occurred after the subscription ended. (This handles edge cases if a stream happened long after the subscription ended, and for the sake of correctness should be included)

Time Complexity Analysis:

The time complexity of this SQL query depends heavily on the database engine's optimization strategies and the size of the tables. In the worst-case scenario (no indexing), the LEFT JOIN could have a time complexity of O(N*M), where N is the number of rows in Subscriptions and M is the number of rows in Streams. However, with appropriate indexes on account_id in both tables, the JOIN operation would likely be closer to O(N + M) or even better, making the overall query relatively efficient. The WHERE clause adds filtering, which doesn't significantly alter the overall time complexity.

Space Complexity Analysis:

The space complexity is primarily determined by the size of the intermediate result set generated by the LEFT JOIN. In the worst case (no matching rows in Streams), the space complexity is proportional to the size of the Subscriptions table, O(N). Again, efficient indexing can significantly improve this as well.