Watch 10 video solutions for Recyclable and Low Fat Products, a easy level problem involving Database. This walkthrough by Start Practicing has 85,570 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Products
+-------------+---------+
| Column Name | Type |
+-------------+---------+
| product_id | int |
| low_fats | enum |
| recyclable | enum |
+-------------+---------+
product_id is the primary key (column with unique values) for this table.
low_fats is an ENUM (category) of type ('Y', 'N') where 'Y' means this product is low fat and 'N' means it is not.
recyclable is an ENUM (category) of types ('Y', 'N') where 'Y' means this product is recyclable and 'N' means it is not.
Write a solution to find the ids of products that are both low fat and recyclable.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Products table: +-------------+----------+------------+ | product_id | low_fats | recyclable | +-------------+----------+------------+ | 0 | Y | N | | 1 | Y | Y | | 2 | N | Y | | 3 | Y | Y | | 4 | N | N | +-------------+----------+------------+ Output: +-------------+ | product_id | +-------------+ | 1 | | 3 | +-------------+ Explanation: Only products 1 and 3 are both low fat and recyclable.
Problem Overview: You are given a Products table containing product_id, low_fats, and recyclable. The task is straightforward: return the IDs of products that are marked as both low fat ('Y') and recyclable ('Y'). This is primarily a filtering problem where you scan records and keep only those matching both conditions.
Approach 1: SQL Filtering Approach (O(n) time, O(1) space)
The most direct solution uses a SQL WHERE clause to filter rows that satisfy both constraints. The query scans the Products table and checks whether low_fats = 'Y' and recyclable = 'Y'. Databases are optimized for this type of filtering, so the engine performs a single pass through the dataset (or uses indexes if available). This approach is ideal when solving the problem directly in SQL or preparing for database-focused interviews involving database queries.
Approach 2: Programmatic Filtering Approach (O(n) time, O(1) space)
If the dataset is represented as objects or rows in application code, iterate through the collection once and check the two attributes for each product. For every entry, evaluate whether both flags equal 'Y'. If the condition holds, append the product_id to the result list. This approach mirrors the SQL filter but is implemented in languages like Python or Java. It relies on a simple linear scan, making it efficient and easy to implement.
Approach 3: Using Hash Maps (O(n) time, O(n) space)
A hash map can store product IDs grouped by their attributes. As you iterate through the dataset, insert entries based on their low_fats and recyclable status. After building the structure, retrieve the IDs that fall into the category where both values are 'Y'. This method is usually unnecessary for this problem but demonstrates how attribute-based grouping can be implemented with constant-time lookups.
Approach 4: Sorting and Counting (O(n log n) time, O(1) extra space)
Another theoretical approach sorts records based on their attribute values so that similar combinations appear together. After sorting, scan the array and collect IDs belonging to the ('Y','Y') group. Sorting introduces an extra O(n log n) cost, so it is less efficient than direct filtering. However, it can be useful when working with datasets that must be ordered for other operations or when applying techniques from sorting algorithms.
Recommended for interviews: The SQL filtering approach is the expected solution for database problems. It demonstrates that you understand how to use conditional filtering in queries and how relational databases process data. The programmatic linear scan is the equivalent approach when solving the problem in a general-purpose language. Brute-force scanning shows basic reasoning, but recognizing that a single-pass filter solves the problem optimally demonstrates practical engineering judgment.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL Filtering Approach | O(n) | O(1) | Best for database queries where filtering rows with conditions is required |
| Programmatic Filtering | O(n) | O(1) | When processing product records in application code |
| Hash Map Grouping | O(n) | O(n) | Useful when grouping products by attributes for multiple lookups |
| Sorting and Counting | O(n log n) | O(1) | When records must be ordered before processing |