Solution Explanation for LeetCode 1149: Article Views II

This problem requires finding all viewers who viewed more than one article on the same day. The solution involves using SQL queries to aggregate and filter data from the Views table.

Approach

The core idea is to group the Views data by viewer_id and view_date, then count the distinct number of article_id within each group. Viewers with more than one distinct article viewed on the same date satisfy the problem's condition.

SQL Solution (MySQL)

SELECT DISTINCT viewer_id AS id
FROM Views
GROUP BY viewer_id, view_date
HAVING COUNT(DISTINCT article_id) > 1
ORDER BY 1;

Explanation:

1. SELECT DISTINCT viewer_id AS id: This selects the unique viewer_id and renames it to id for the output. DISTINCT ensures that each viewer is listed only once, even if they appear multiple times in the grouped results.

2. FROM Views: This specifies that we're querying the Views table.

3. GROUP BY viewer_id, view_date: This groups the rows based on both viewer_id and view_date. This is crucial for counting articles viewed by the same person on the same day.

4. HAVING COUNT(DISTINCT article_id) > 1: This is a crucial filter. COUNT(DISTINCT article_id) counts the number of unique articles viewed within each group (viewer and date). The HAVING clause filters out groups where this count is less than or equal to 1, leaving only those viewers who saw more than one distinct article on a given day.

5. ORDER BY 1: This sorts the result set in ascending order based on the first column (id).

Time Complexity Analysis

The time complexity of this SQL query is dominated by the GROUP BY and HAVING clauses. The time complexity of grouping and aggregation is generally considered to be O(N log N) or O(N), where N is the number of rows in the Views table, depending on the specific database implementation and indexing. The HAVING clause then filters the results, which takes linear time relative to the size of the grouped data. Therefore, the overall time complexity is approximately O(N log N) in the worst case. The exact time complexity can depend heavily on database optimizations and indexes.

Space Complexity Analysis

The space complexity depends on the size of the intermediate results produced during the grouping and aggregation process. In the worst case, if there are many viewers and many views per viewer per day, this could use a significant amount of temporary storage. However, this is typically handled efficiently by the database engine itself, so the space complexity is hard to define precisely without specifics about the database implementation and available resources. We can approximate it as O(M) where M is the number of unique (viewer_id, view_date) pairs. This is because the database needs to store the aggregated counts for each unique pair.