{x}
blog image

Group Sold Products By The Date

Table Activities:

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| sell_date   | date    |
| product     | varchar |
+-------------+---------+
There is no primary key (column with unique values) for this table. It may contain duplicates.
Each row of this table contains the product name and the date it was sold in a market.

 

Write a solution to find for each date the number of different products sold and their names.

The sold products names for each date should be sorted lexicographically.

Return the result table ordered by sell_date.

The result format is in the following example.

 

Example 1:

Input: 
Activities table:
+------------+------------+
| sell_date  | product     |
+------------+------------+
| 2020-05-30 | Headphone  |
| 2020-06-01 | Pencil     |
| 2020-06-02 | Mask       |
| 2020-05-30 | Basketball |
| 2020-06-01 | Bible      |
| 2020-06-02 | Mask       |
| 2020-05-30 | T-Shirt    |
+------------+------------+
Output: 
+------------+----------+------------------------------+
| sell_date  | num_sold | products                     |
+------------+----------+------------------------------+
| 2020-05-30 | 3        | Basketball,Headphone,T-shirt |
| 2020-06-01 | 2        | Bible,Pencil                 |
| 2020-06-02 | 1        | Mask                         |
+------------+----------+------------------------------+
Explanation: 
For 2020-05-30, Sold items were (Headphone, Basketball, T-shirt), we sort them lexicographically and separate them by a comma.
For 2020-06-01, Sold items were (Pencil, Bible), we sort them lexicographically and separate them by a comma.
For 2020-06-02, the Sold item is (Mask), we just return it.

Solution Explanation for LeetCode 1484: Group Sold Products By The Date

This problem requires aggregating data from the Activities table to find the number of distinct products sold and their names for each date. The solution involves using SQL's aggregate functions and string manipulation.

Approach

The core idea is to group the data by sell_date and then use aggregate functions within each group.

  1. Grouping: The GROUP BY sell_date clause groups the rows based on the selling date. This allows us to perform calculations for each individual date.

  2. Counting Distinct Products: COUNT(DISTINCT product) counts the number of unique products sold on each date. This gives us the num_sold value.

  3. Concatenating Product Names: GROUP_CONCAT(DISTINCT product) concatenates the distinct product names for each date, separated by commas. This provides the products string. The DISTINCT keyword ensures that each product is listed only once, even if it was sold multiple times on the same day.

  4. Ordering: ORDER BY sell_date sorts the final result set in ascending order of the selling dates.

Time and Space Complexity Analysis

  • Time Complexity: The time complexity is dominated by the GROUP BY operation. In general, a GROUP BY operation on a table with N rows takes O(N log N) or O(N) time depending on the specific database implementation and indexing. The GROUP_CONCAT operation also has a time complexity related to the length of the resulting string and number of groups. This could be considered O(N * M), where M is the maximum number of distinct products on a single day. Overall the complexity can be approximated to O(N log N) or O(N)

  • Space Complexity: The space complexity depends on the size of the output. The space required to store the intermediate results of the GROUP BY operation and the final result set is proportional to the number of distinct selling dates and the maximum number of products sold on a single day. This would be considered O(K * M), where K is the number of distinct selling dates and M is the maximum number of distinct products on a single day.

Code in MySQL

SELECT
    sell_date,
    COUNT(DISTINCT product) AS num_sold,
    GROUP_CONCAT(DISTINCT product ORDER BY product) AS products -- added ORDER BY for lexicographical sorting
FROM Activities
GROUP BY sell_date
ORDER BY sell_date;

Note: I've added ORDER BY product inside GROUP_CONCAT to ensure that the product names within each products string are lexicographically sorted as required by the problem statement.

This query efficiently addresses the problem, providing the required information in the specified format. The use of GROUP_CONCAT is a concise way to achieve the string concatenation for each date. The overall solution is optimized for performance considering the aggregate functions used and the nature of the problem.