List the Products Ordered in a Period

Difficulty: Easy | Acceptance: 71.70% | Paid: No Topics: Database

Table: Products

+---------------+---------+ | Column Name | Type | +---------------+---------+ | product_id | int | | product_name | varchar | | product_category | varchar | +---------------+---------+ product_id is the primary key for this table. This table contains data about the company’s products.

Table: Orders

+---------------+---------+ | Column Name | Type | +---------------+---------+ | order_id | int | | product_id | int | | order_date | date | +---------------+---------+ order_id is the primary key for this table. product_id is a foreign key to Products table. order_date is in the format ‘YYYY-MM-DD’.

Write a solution to list the names of the products and the category they belong to for each of the products ordered in February 2020.

Return the result table in any order.

The result format is in the following example.

• Examples
• Constraints
• Approach 1: Brute Force Simulation
• Approach 2: Hash Map Join

Examples

Example 1

Input:

Products table: +-------------+-----------------------+------------------+ | product_id | product_name | product_category | +-------------+-----------------------+------------------+ | 1 | Leetcode | Computer | | 2 | GeeksforGeeks | Computer | | 3 | HackerRank | Computer | | 4 | InterviewBit | Computer | | 5 | CodeWars | Computer | +-------------+-----------------------+------------------+

Orders table: +-------------+-------------+-------------+ | order_id | product_id | order_date | +-------------+-------------+-------------+ | 1 | 1 | 2020-02-05 | | 2 | 1 | 2020-02-10 | | 3 | 3 | 2020-02-18 | | 4 | 4 | 2020-02-28 | | 5 | 4 | 2020-03-01 | | 6 | 5 | 2020-03-12 | +-------------+-------------+-------------+

Output: +-----------------------+------------------+ | product_name | product_category | +-----------------------+------------------+ | Leetcode | Computer | | HackerRank | Computer | | InterviewBit | Computer | +-----------------------+------------------+

Explanation: Products with product_id 1, 3, and 4 were ordered in February 2020. Product with product_id 2 was not ordered in February 2020. Product with product_id 5 was ordered in March 2020.

Constraints

The input tables will contain at least one order in February 2020.

Approach 1: Brute Force Simulation

Intuition Simulate the database join by iterating through each order, checking if it falls within the date range, and then scanning the entire product list to find the matching product details.

Steps

• Initialize an empty set to store unique product results.
• Iterate through each order in the Orders list.
• Check if the order_date is between ‘2020-02-01’ and ‘2020-02-29’.
• If valid, iterate through the Products list to find the product with the matching product_id.
• If found, add the product_name and product_category to the set.
• Convert the set to a list and sort it by product_name.
• Return the sorted list.

class Solution:
    def listProducts(self, products: list[list[str]], orders: list[list[str]]) -> list[list[str]]:
        res_set = set()
        for o in orders:
            date = o[2]
            if "2020-02-01" <= date <= "2020-02-29":
                pid = o[1]
                for p in products:
                    if p[0] == pid:
                        res_set.add((p[1], p[2]))
                        break
        res = list(res_set)
        res.sort(key=lambda x: x[0])
        return res

Complexity

• Time: O(N * M) where N is the number of orders and M is the number of products.
• Space: O(N) to store the result set.
• Notes: Simple to implement but inefficient for large datasets due to the nested loop.

Approach 2: Hash Map Join

Intuition Optimize the lookup process by using a hash map (dictionary) to store product information, keyed by product_id. This allows for O(1) average time complexity when retrieving product details for an order.

Steps

• Create a hash map mapping product_id to a list containing product_name and product_category.
• Initialize an empty set to store unique product results.
• Iterate through each order in the Orders list.
• Check if the order_date is between ‘2020-02-01’ and ‘2020-02-29’.
• If valid, check if the product_id exists in the hash map.
• If it exists, retrieve the details and add them to the set.
• Convert the set to a list and sort it by product_name.
• Return the sorted list.

class Solution:
    def listProducts(self, products: list[list[str]], orders: list[list[str]]) -> list[list[str]]:
        prod_map = {p[0]: (p[1], p[2]) for p in products}
        res_set = set()
        for o in orders:
            date = o[2]
            if "2020-02-01" <= date <= "2020-02-29":
                pid = o[1]
                if pid in prod_map:
                    res_set.add((prod_map[pid][0], prod_map[pid][1]))
        res = list(res_set)
        res.sort(key=lambda x: x[0])
        return res

Complexity

• Time: O(N + M) where N is the number of orders and M is the number of products.
• Space: O(M) to store the hash map of products.
• Notes: Much faster than the brute force approach for large datasets, trading space for time.