Abstract / Summary

Find products that are both recyclable and low fat from two lists and return them sorted alphabetically.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 89% (2+ million submissions).

Typical patterns to solve this problem:

• Database

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided SQL statement retrieves the identifiers of products that satisfy two boolean-style attributes: the product must be marked as low-fat and also be recyclable. The query is straightforward, consisting of a single SELECT clause with two predicates combined by an AND. Despite its simplicity, the statement touches on several important aspects of relational query processing, including column projection, predicate evaluation, and the use of indexes to accelerate row filtering.

Key Steps

Step 1 - Column Projection

The query begins by specifying the column to be returned:

SELECT product_id

Only the primary key (or unique identifier) of each qualifying product is needed. By limiting the output to a single column, the database engine can avoid fetching additional column data from the storage layer, which reduces I/O and memory consumption for the result set.

Step 2 - Source Table Identification

The FROM clause identifies the table that holds the product records:

FROM Products

All subsequent filtering operations are applied to rows drawn from this table. The engine will locate the table’s metadata, including column definitions and any associated indexes, before proceeding with predicate evaluation.

Step 3 - Predicate Evaluation - Low-Fat Filter

The first predicate restricts rows to those where the low_fats column contains the character 'Y':

WHERE low_fats = 'Y'

During execution, the engine evaluates this condition for each candidate row. If an index exists on low_fats, the engine can perform an index seek to directly locate rows that match 'Y', bypassing a full table scan.

Step 4 - Predicate Evaluation - Recyclable Filter

The second predicate further narrows the result set to rows where recyclable also equals 'Y':

AND recyclable = 'Y'

When both predicates are present, the optimizer can combine them into a single index lookup if a composite index covering both columns is available. Otherwise, it may apply one predicate using an index and filter the remaining rows with the second predicate.

Step 5 - Result Assembly

After both predicates have been satisfied, the engine assembles the final result set containing only the product_id values. Because the projection is limited to a single column, the engine can often return the identifiers directly from the index structure without accessing the full row data.

Edge Cases Handled

The query implicitly addresses several data-quality scenarios:

• Case Sensitivity - By comparing to the literal 'Y', the condition matches only rows where the column value exactly matches the uppercase character. If the column stores lowercase 'y' or mixed-case values, those rows will be excluded, ensuring a deterministic result set.

• Null Values - In SQL, any comparison with NULL yields an unknown result, which the WHERE clause treats as false. Consequently, rows where low_fats or recyclable are NULL are automatically filtered out, preventing accidental inclusion of incomplete records.

• Unexpected Characters - If a row contains a value other than 'Y' (for example, 'N', 'YES', or any numeric code), the predicate fails, and the row is omitted. This strict equality check guarantees that only explicitly marked products are returned.

• Duplicate Identifiers - Should the product_id column contain duplicate values (unlikely if it is a primary key), the query will return each matching duplicate. The projection does not enforce uniqueness beyond what the underlying schema defines.

Performance Optimizations Observed

Even though the statement is concise, several optimization opportunities are naturally leveraged by modern relational engines:

• Single-Column Index - An index on product_id alone can serve as a covering index for this query if the index also stores the low_fats and recyclable columns as included columns. In that case, the engine can satisfy the entire query from the index without touching the base table.

• Composite Index on Filter Columns - A composite index on (low_fats, recyclable, product_id) enables the engine to perform a single index seek that simultaneously satisfies both predicates and provides the projected column. This reduces the number of logical reads dramatically compared to evaluating each predicate separately.

• Predicate Pushdown - The optimizer pushes the WHERE conditions down to the storage engine, allowing early elimination of non-matching rows. This minimizes the amount of data that must be processed in later stages such as sorting or aggregation (none are present here, but the principle still applies).

• Statistical Awareness - The query planner uses column statistics to estimate the selectivity of each predicate. If the 'Y' value is rare for either attribute, the planner may choose an index seek on that column first, then apply the second predicate as a residual filter, thereby reducing the intermediate row count.

• Parallel Execution - For large tables, the engine may split the scan of the qualifying rows across multiple threads, especially when the predicates are not highly selective. The projection to a single column keeps the per-thread memory footprint low, facilitating efficient parallelism.

• Result Caching - If the same query is executed repeatedly with identical predicates, the database may cache the result set or the execution plan, allowing subsequent runs to bypass full predicate evaluation and retrieve the identifiers directly from the cache.

By aligning the query structure with these optimization mechanisms-particularly through the use of appropriate indexes-the statement can achieve rapid response times even on tables containing millions of product records.

Imagine you have a giant toy chest called Products that is filled with all sorts of playthings. Each toy has a little sticker on it that tells you if it is good for the Earth. Some toys have a special sticker that says the toy is made with low fat, which is the letter Y, and another sticker that says you can recycle it, which is also the letter Y. This code acts like a very smart robot helper. It goes through the toy chest one by one and looks for the toys that have both of those special stickers. When the robot finds a toy that is both low fat and recyclable, it writes down the secret product code number for that toy on a piece of paper so you know exactly which ones to pick out.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		C++	Java	Python	TS
	WalkCCC	SQL
	leetcode.ca	SQL			Python
	Progiez		C++	Java	Python
github	everthis	SQL
	muhammadfarhankt	SQL
	suxrobGM	SQL
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	SQL
leetcode.ca	Python, SQL
Progiez	C++, Java, Python
everthis	SQL
muhammadfarhankt	SQL
suxrobGM	SQL

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality