Difficulty: Easy | Acceptance: 47.60% | Paid: No Topics: Database
Table: Sales
+-------------+-------+ | Column Name | Type | +-------------+-------+ | sale_id | int | | product_id | int | | year | int | | quantity | int | | price | int | +-------------+-------+ (sale_id, year) is the primary key of this table. product_id is a foreign key to Product table. Each row of this table shows a sale on the product product_id in a certain year. Note that the price is per unit.
Table: Product
+--------------+---------+ | Column Name | Type | +--------------+---------+ | product_id | int | | product_name | varchar | +--------------+---------+ product_id is the primary key of this table. Each row of this table indicates the product name of a product.
Write an SQL query to report the products that were only sold in the first year of sales (2019).
Return the result table in any order.
The query result format is in the following example.
- Examples
- Constraints
- Approach 1: Hash Map Grouping
- Approach 2: Set Difference
Examples
Example 1:
Input:
Sales table: +-----------+------------+----------+-------+-------+ | sale_id | product_id | year | quantity | price | +-----------+------------+----------+-------+-------+ | 1 | 100 | 2008 | 10 | 5000 | | 2 | 100 | 2009 | 12 | 5000 | | 7 | 200 | 2011 | 15 | 9000 | +-----------+------------+----------+-------+-------+
Product table: +------------+--------------+ | product_id | product_name | +------------+--------------+ | 100 | Nokia | | 200 | Apple | | 300 | Samsung | +------------+--------------+
Output: +------------+--------------+ | product_id | product_name | +------------+--------------+ | 100 | Nokia | +------------+--------------+
Explanation: The product with id 100 was only sold in the first year (2008), while the product with id 200 was sold in years 2009 and 2011. The product with id 300 was not sold at all.
Example 2:
Input:
Sales table: +-----------+------------+----------+-------+-------+ | sale_id | product_id | year | quantity | price | +-----------+------------+----------+-------+-------+ | 1 | 100 | 2019 | 10 | 5000 | | 2 | 100 | 2020 | 12 | 5000 | | 3 | 200 | 2019 | 15 | 9000 | +-----------+------------+----------+-------+-------+
Product table: +------------+--------------+ | product_id | product_name | +------------+--------------+ | 100 | Nokia | | 200 | Apple | +------------+--------------+
Output: +------------+--------------+ | product_id | product_name | +------------+--------------+ | 200 | Apple | +------------+--------------+
Explanation: The product with id 100 was sold in both 2019 and 2020. The product with id 200 was sold only in 2019.
Constraints
There are no specific constraints provided for this problem other than the table structures.
Approach 1: Hash Map Grouping
Intuition We can iterate through the sales records and maintain a map (dictionary) where the key is the product_id and the value is a set of years in which that product was sold. After processing all sales, we filter the map to find products where the set of years contains 2019 but does not contain 2020. Finally, we join this result with the Product table to get the product names.
Steps
- Create a map to store product_id -> set of years.
- Iterate through the Sales list. For each record, add the year to the set corresponding to the product_id.
- Create a map for product_id -> product_name from the Product list.
- Iterate through the sales map. If a product’s year set contains 2019 and not 2020, add it to the result.
- Return the result list containing product_id and product_name.
from typing import List
class Solution:
def salesAnalysis(self, sales: List[List[int]], products: List[List[str]]) -> List[List[str]]:
# Map product_id to set of years sold
sales_map = {}
for s in sales:
pid = s[1]
year = s[2]
if pid not in sales_map:
sales_map[pid] = set()
sales_map[pid].add(year)
# Map product_id to product_name
product_map = {}
for p in products:
pid = int(p[0])
name = p[1]
product_map[pid] = name
result = []
for pid, years in sales_map.items():
if 2019 in years and 2020 not in years:
result.append([str(pid), product_map[pid]])
return result
Complexity
- Time: O(N + M) where N is the number of sales and M is the number of products.
- Space: O(N + M) to store the maps.
- Notes: This approach is efficient and straightforward, mimicking the SQL GROUP BY and HAVING logic.
Approach 2: Set Difference
Intuition
We can separate the products sold in 2019 and those sold in 2020 into two distinct sets. The answer is the set difference: products sold in 2019 minus products sold in 2020. This corresponds to the SQL logic of WHERE year = 2019 AND product_id NOT IN (SELECT product_id FROM Sales WHERE year = 2020).
Steps
- Create a set for products sold in 2019.
- Create a set for products sold in 2020.
- Iterate through the Sales list and populate these sets based on the year.
- Iterate through the 2019 set. If a product ID is not in the 2020 set, add it to the result.
- Join with the Product table to get names.
from typing import List
class Solution:
def salesAnalysis(self, sales: List[List[int]], products: List[List[str]]) -> List[List[str]]:
sold_2019 = set()
sold_2020 = set()
for s in sales:
pid = s[1]
year = s[2]
if year == 2019:
sold_2019.add(pid)
elif year == 2020:
sold_2020.add(pid)
product_map = {int(p[0]): p[1] for p in products}
result = []
for pid in sold_2019:
if pid not in sold_2020:
result.append([str(pid), product_map[pid]])
return result
Complexity
- Time: O(N + M) where N is the number of sales and M is the number of products.
- Space: O(N + M) to store the sets and map.
- Notes: This approach is slightly more memory efficient if we only care about 2019 and 2020, as we don’t store years for other products.