LeetCode 1757 - Recyclable and Low Fat Products

LeetCode Problem 1757

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem gives us a database table named Products. Each row represents a product and contains three columns:

Column	Meaning
product_id	Unique identifier for the product
low_fats	'Y' if the product is low fat, otherwise 'N'
recyclable	'Y' if the product is recyclable, otherwise 'N'

The task is to return the IDs of products that satisfy both conditions simultaneously:

1. The product is low fat
2. The product is recyclable

In other words, we only want rows where:

low_fats = 'Y'
AND recyclable = 'Y'

The output should contain a single column:

product_id

The order of the result does not matter.

The constraints are very small conceptually because this is an introductory SQL filtering problem. The table already guarantees that product_id is unique because it is the primary key. The values for low_fats and recyclable are restricted to only 'Y' and 'N', so we do not need to handle invalid values.

An important observation is that the problem does not ask us to modify data, aggregate rows, or join multiple tables. We simply need to filter rows based on two conditions.

Some edge cases are worth thinking about:

• No products satisfy both conditions, the result should be empty.
• Every product satisfies both conditions, all IDs should be returned.
• Products may satisfy only one condition, those rows must not appear in the result.
• Since the order is arbitrary, sorting is unnecessary.

Approaches

Brute Force Approach

The brute force way to think about this problem is to examine every row in the Products table one by one. For each product, we check:

• Is low_fats = 'Y'?
• Is recyclable = 'Y'?

If both are true, we include the product_id in the result.

This approach is guaranteed to work because every row is explicitly checked against the required conditions. No product can be missed, and no invalid product can be included.

In practice, this is already efficient because filtering rows in a table is a linear operation. Since the task itself is simple, there is no fundamentally faster approach than scanning the relevant rows.

Optimal Approach

The optimal solution uses a SQL WHERE clause to filter the table directly inside the database engine.

The key insight is that SQL is designed specifically for declarative filtering operations. Instead of manually iterating through rows in application code, we let the database engine return only the matching rows.

The condition we need is:

low_fats = 'Y' AND recyclable = 'Y'

This solution is concise, efficient, and idiomatic SQL.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan every row and manually check conditions
Optimal	O(n)	O(1)	Use SQL filtering with a WHERE clause

Algorithm Walkthrough

1. Start with the Products table containing all products.
2. Apply a filter condition using the SQL WHERE clause.
3. Check whether low_fats equals 'Y'. This ensures the product is low fat.
4. Check whether recyclable equals 'Y'. This ensures the product is recyclable.
5. Use the AND operator so that only rows satisfying both conditions are returned.
6. Select only the product_id column because the problem asks for product IDs, not the full rows.

The final query becomes:

SELECT product_id
FROM Products
WHERE low_fats = 'Y'
AND recyclable = 'Y';

Why it works

The algorithm works because every product row is evaluated against the exact requirements from the problem statement. A row is included only if both boolean conditions are true. Since SQL filtering is deterministic and exhaustive over the table rows, the result contains precisely the recyclable and low fat products.

Python Solution

Although this is a database problem and LeetCode expects a SQL query, the following Python example demonstrates the same logic programmatically.

from typing import List, Dict

class Solution:
    def recyclableAndLowFat(
        self,
        products: List[Dict[str, str]]
    ) -> List[int]:
        result = []

        for product in products:
            if (
                product["low_fats"] == "Y"
                and product["recyclable"] == "Y"
            ):
                result.append(product["product_id"])

        return result

The implementation iterates through every product in the input list. For each product, it checks whether both required fields are equal to "Y".

If the conditions are satisfied, the product ID is added to the result list. After processing all products, the result list is returned.

This mirrors the SQL logic exactly. The if condition corresponds directly to the SQL WHERE clause.

For completeness, the actual LeetCode SQL solution is:

SELECT product_id
FROM Products
WHERE low_fats = 'Y'
AND recyclable = 'Y';

Go Solution

package main

type Product struct {
	ProductID  int
	LowFats    string
	Recyclable string
}

func recyclableAndLowFat(products []Product) []int {
	result := []int{}

	for _, product := range products {
		if product.LowFats == "Y" && product.Recyclable == "Y" {
			result = append(result, product.ProductID)
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version. We iterate through the slice of products and append matching product IDs to the result slice.

One small Go-specific detail is that slices are dynamically resized when using append. Unlike Python lists, Go slices distinguish between nil and empty slices, but either representation works correctly here because the problem only cares about returned values.

For completeness, the actual LeetCode SQL solution is:

SELECT product_id
FROM Products
WHERE low_fats = 'Y'
AND recyclable = 'Y';

Worked Examples

Example 1

Input table:

product_id	low_fats	recyclable
0	Y	N
1	Y	Y
2	N	Y
3	Y	Y
4	N	N

We process each row one at a time.

Current Product	low_fats == 'Y'	recyclable == 'Y'	Include?	Result
0	Yes	No	No	[]
1	Yes	Yes	Yes	[1]
2	No	Yes	No	[1]
3	Yes	Yes	Yes	[1, 3]
4	No	No	No	[1, 3]

Final output:

product_id
1
3

Only products 1 and 3 satisfy both conditions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every product row is checked once
Space	O(1) excluding output	Only a small amount of extra memory is used

The algorithm performs a single pass through the table. Each row requires constant work because we only compare two values. Therefore, the total runtime grows linearly with the number of rows.

The auxiliary space usage is constant because no additional data structures proportional to the input size are created. The output list itself is not counted toward auxiliary space complexity.

Test Cases

from typing import List, Dict

class Solution:
    def recyclableAndLowFat(
        self,
        products: List[Dict[str, str]]
    ) -> List[int]:
        result = []

        for product in products:
            if (
                product["low_fats"] == "Y"
                and product["recyclable"] == "Y"
            ):
                result.append(product["product_id"])

        return result

solution = Solution()

# Provided example
assert solution.recyclableAndLowFat([
    {"product_id": 0, "low_fats": "Y", "recyclable": "N"},
    {"product_id": 1, "low_fats": "Y", "recyclable": "Y"},
    {"product_id": 2, "low_fats": "N", "recyclable": "Y"},
    {"product_id": 3, "low_fats": "Y", "recyclable": "Y"},
    {"product_id": 4, "low_fats": "N", "recyclable": "N"},
]) == [1, 3]  # Standard mixed case

# No matching products
assert solution.recyclableAndLowFat([
    {"product_id": 1, "low_fats": "N", "recyclable": "N"},
    {"product_id": 2, "low_fats": "N", "recyclable": "Y"},
]) == []  # Empty result

# All products match
assert solution.recyclableAndLowFat([
    {"product_id": 1, "low_fats": "Y", "recyclable": "Y"},
    {"product_id": 2, "low_fats": "Y", "recyclable": "Y"},
]) == [1, 2]  # Every row satisfies conditions

# Single product matching
assert solution.recyclableAndLowFat([
    {"product_id": 10, "low_fats": "Y", "recyclable": "Y"},
]) == [10]  # Single valid row

# Single product not matching
assert solution.recyclableAndLowFat([
    {"product_id": 10, "low_fats": "Y", "recyclable": "N"},
]) == []  # Single invalid row

# Empty input
assert solution.recyclableAndLowFat([]) == []  # No products at all

Test	Why
Mixed valid and invalid rows	Verifies normal filtering behavior
No matching products	Ensures empty results are handled correctly
All matching products	Confirms all valid rows are returned
Single matching row	Tests smallest non-empty valid input
Single non-matching row	Tests smallest non-empty invalid input
Empty input	Ensures no crashes on empty datasets

Edge Cases

No Products Match the Conditions

A common edge case is when every product fails at least one condition. For example, all products may be non-recyclable or not low fat.

A buggy implementation might accidentally use OR instead of AND, which would incorrectly include partially matching products. The current implementation avoids this by requiring both conditions simultaneously.

Empty Input Table

The table may contain zero rows. In this case, the correct result is simply an empty result set.

The implementation handles this naturally because iterating over an empty collection performs zero iterations, leaving the result empty.

Products Matching Only One Condition

Some products may be low fat but not recyclable, or recyclable but not low fat.

This is important because a naive implementation could accidentally treat either condition as sufficient. The implementation explicitly checks:

product["low_fats"] == "Y" and product["recyclable"] == "Y"

This guarantees that only products satisfying both requirements are included.

All Products Match

Another important edge case occurs when every row satisfies the conditions. The implementation must return all product IDs without skipping any rows.

Since the algorithm independently checks each row and appends every valid ID, all qualifying products are correctly returned.