Solution Explanation for LeetCode Problem 1322: Ads Performance

This problem requires calculating the Click-Through Rate (CTR) for each ad. The CTR is defined as (number of clicks / (number of clicks + number of views)) * 100. The solution involves aggregating data from the Ads table and performing calculations to achieve this.

Approach

The core idea is to group the data by ad_id and then calculate the CTR for each group. We'll use aggregate functions like SUM() and conditional aggregation to count clicks and views separately. The IFNULL() function handles cases where there are no clicks or views for an ad, preventing division by zero errors. Finally, we round the result to two decimal places using ROUND() and order the results as specified.

SQL Solution (MySQL)

SELECT
    ad_id,
    ROUND(IFNULL(SUM(action = 'Clicked') / SUM(action IN('Clicked', 'Viewed')) * 100, 0), 2) AS ctr
FROM Ads
GROUP BY 1
ORDER BY 2 DESC, 1;

Explanation:

1. SELECT ad_id, ...: This selects the ad_id for each ad.

2. ROUND(IFNULL(SUM(action = 'Clicked') / SUM(action IN('Clicked', 'Viewed')) * 100, 0), 2): This is the core calculation. Let's break it down:

   • SUM(action = 'Clicked'): This counts the number of rows where action is 'Clicked' for each ad_id.
   • SUM(action IN('Clicked', 'Viewed')): This counts the number of rows where action is either 'Clicked' or 'Viewed' for each ad_id.
   • /: This divides the click count by the sum of click and view counts.
   • * 100: This multiplies the result by 100 to express CTR as a percentage.
   • IFNULL(..., 0): This handles the case where there are no clicks or views (the denominator is zero). It replaces NULL with 0 to avoid errors.
   • ROUND(..., 2): This rounds the final CTR to two decimal places.

3. FROM Ads: This specifies the table to use.

4. GROUP BY 1: This groups the results by ad_id (1 refers to the first column in the SELECT statement).

5. ORDER BY 2 DESC, 1: This orders the results first by ctr in descending order (highest CTR first) and then by ad_id in ascending order (to break ties).

Time Complexity Analysis

The time complexity of this SQL query is dominated by the GROUP BY operation. The time complexity of GROUP BY is generally O(N log N) or O(N), where N is the number of rows in the Ads table, depending on the specific database implementation and indexing. The other operations (SUM, IFNULL, ROUND) have linear time complexity O(N). Therefore, the overall time complexity is O(N log N) or O(N).

Space Complexity Analysis

The space complexity is determined by the size of the intermediate results during the GROUP BY operation and the final result set. In the worst case, the space complexity is O(N), where N is the number of unique ad_id values. This is because we need to store the aggregated data for each ad. Therefore, the overall space complexity is O(N).