Solution Explanation for LeetCode 1113: Reported Posts

This problem requires querying a database table (Actions) to find the number of posts reported for each reason on a specific date ("2019-07-04"). The solution uses SQL to achieve this efficiently.

Approach

The solution directly leverages SQL's aggregate and filtering capabilities. We filter the Actions table to include only entries where:

1. action_date is '2019-07-04' (yesterday).
2. action is 'report'.

Then, we group the results by extra (the report reason) and count the distinct post_id values within each group. COUNT(DISTINCT post_id) ensures that we count each post only once, even if it has multiple reports with the same reason. Finally, the result is presented with the report reason and its count.

SQL Code (MySQL)

SELECT extra AS report_reason, COUNT(DISTINCT post_id) AS report_count
FROM Actions
WHERE action_date = '2019-07-04' AND action = 'report'
GROUP BY 1;

Explanation:

• SELECT extra AS report_reason, COUNT(DISTINCT post_id) AS report_count: This selects the extra column (report reason) and renames it to report_reason. It also counts the distinct post_id values (number of unique posts reported) and renames it to report_count.
• FROM Actions: This specifies that we are querying the Actions table.
• WHERE action_date = '2019-07-04' AND action = 'report': This filters the rows to include only those where the action date is '2019-07-04' and the action is 'report'.
• GROUP BY 1: This groups the results by the first column in the SELECT statement (which is report_reason), allowing us to count reports for each reason.

Time Complexity Analysis

The time complexity of this SQL query depends on the size of the Actions table (N). The filtering and grouping operations are typically done using optimized database indexing and algorithms. In the best-case scenario (with appropriate indexing on action_date and action), the time complexity would be approximately O(N), because it might need to scan the whole table in the worst-case. However, the actual performance would depend on the database system's specific optimization techniques and indexing.

Space Complexity Analysis

The space complexity is determined by the size of the intermediate result set (the number of unique report reasons and their counts), which is considerably smaller than the size of the Actions table in most realistic scenarios. Therefore, the space complexity is relatively low and can be considered O(M), where M is the number of distinct report reasons.

This SQL solution provides an efficient way to solve the problem. The use of COUNT(DISTINCT post_id) avoids overcounting and directly provides the desired output. The time and space efficiency depend primarily on the database system's optimization capabilities and the presence of suitable indexes.