Find Products with Valid Serial Numbers solution and explanation
2 more videos on this problem
Leetcode 3465 - Regular Expressions (RegEx) in SQL - Find Products With Valid Serial NumbersEveryday Data Science · 8:10 · 1K views
Find Products with Valid Serial Numbers – LeetCode 3465 Explained (PostgreSQL Tutorial)Sumanshu Nankana · 13:15 · 93 views
LeetCode 3465: Find Products with Valid Serial Numbersmatjazcodes · 5:04 · 44 views
The problem
Table: products
+--------------+------------+ | Column Name | Type | +--------------+------------+ | product_id | int | | product_name | varchar | | description | varchar | +--------------+------------+ (product_id) is the unique key for this table. Each row in the table represents a product with its unique ID, name, and description.
Write a solution to find all products whose description contains a valid serial number pattern. A valid serial number follows these rules:
- It starts with the letters SN (case-sensitive).
- Followed by exactly
4digits. - It must have a hyphen (-) followed by exactly
4digits. - The serial number must be within the description (it may not necessarily start at the beginning).
Return the result table ordered by product_id in ascending order.
The result format is in the following example.
Example:
Input:
products table:
+------------+--------------+------------------------------------------------------+
| product_id | product_name | description |
+------------+--------------+------------------------------------------------------+
| 1 | Widget A | This is a sample product with SN1234-5678 |
| 2 | Widget B | A product with serial SN9876-1234 in the description |
| 3 | Widget C | Product SN1234-56789 is available now |
| 4 | Widget D | No serial number here |
| 5 | Widget E | Check out SN4321-8765 in this description |
+------------+--------------+------------------------------------------------------+
Output:
+------------+--------------+------------------------------------------------------+
| product_id | product_name | description |
+------------+--------------+------------------------------------------------------+
| 1 | Widget A | This is a sample product with SN1234-5678 |
| 2 | Widget B | A product with serial SN9876-1234 in the description |
| 5 | Widget E | Check out SN4321-8765 in this description |
+------------+--------------+------------------------------------------------------+
Explanation:
- Product 1: Valid serial number SN1234-5678
- Product 2: Valid serial number SN9876-1234
- Product 3: Invalid serial number SN1234-56789 (contains 5 digits after the hyphen)
- Product 4: No serial number in the description
- Product 5: Valid serial number SN4321-8765
The result table is ordered by product_id in ascending order.
Approach overview
Problem Overview: You have a Products table with a description column. Return the product_id and product_name of every product whose description contains a valid serial number, ordered by product_id. A valid serial number is SN followed by exactly four digits, a hyphen, and four more digits, and it must stand alone as a token. Text like XSN1234-5678 or SN1234-56789 does not count.
Approach 1: Manual String Scan (O(n * L) time, O(1) extra space per row)
Scan each description character by character looking for the literal SN. At each match, check the next 9 characters for the pattern dddd-dddd. Then check the character before SN and the character after the last digit. Both must be non-alphanumeric or a string boundary. This works in any SQL dialect without regex support, but the boundary checks are easy to get wrong. The cost is O(L) per description, where L is the description length, so the full query runs in O(n * L) across n rows.
Approach 2: Regex Matching (O(n * L) time, O(1) extra space per row)
Compile one pattern: \bSN[0-9]{4}-[0-9]{4}\b. The \b anchors enforce the token boundary for you. In MySQL 8, use description REGEXP '\\bSN[0-9]{4}-[0-9]{4}\\b'. In Pandas, use df[df['description'].str.contains(r'\bSN\d{4}-\d{4}\b', regex=True)], then sort by product_id. The regex engine does the same scanning as Approach 1, but the pattern is short and the boundary logic is declarative. This is the approach available on FleetCode, and it is the one you should write in an interview or on the job.
Recommended for interviews: Interviewers expect you to name the pattern precisely before writing anything. The manual scan shows you understand what the regex engine does under the hood. The regex solution with correct word boundaries and an ORDER BY on product_id shows you can write production-quality SQL. Missing the boundary requirement is the most common reason candidates fail this problem. Review the related database and string topics if pattern matching is new to you.
Solution
Thinking
A description must contain a serial of the form
SN, four digits, a hyphen, and four more digits. A raw substring search can glue that pattern to neighboring alphanumerics.Word boundaries
\bkeep the serial a standalone token.Filter with
\bSN[0-9]{4}-[0-9]{4}\band sort byproduct_id.
According to the problem statement, we need to find all products that contain a valid serial number, and the rules for a valid serial number are:
- Starts with
SN(case-sensitive). - Followed by 4 digits.
- Must have a hyphen
-, followed by 4 digits.
Based on the above rules, we can use a regular expression to match valid serial numbers, then filter out the products that contain valid serial numbers, and finally sort them in ascending order by product_id.
# Write your MySQL query statement below
SELECT product_id, product_name, description
FROM products
WHERE description REGEXP '(?-i)\\bSN[0-9]{4}-[0-9]{4}\\b'
ORDER BY 1;import pandas as pd
def find_valid_serial_products(products: pd.DataFrame) -> pd.DataFrame:
valid_pattern = r"\bSN[0-9]{4}-[0-9]{4}\b"
valid_products = products[
products["description"].str.contains(valid_pattern, regex=True)
]
valid_products = valid_products.sort_values(by="product_id")
return valid_productsComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Manual String Scan | O(n * L) | O(1) | Database lacks regex support or you need to avoid regex dependencies |
| Regex Matching | O(n * L) | O(1) | General case in MySQL or Pandas, cleanest and most readable |
Frequently asked questions
Find Products with Valid Serial Numbers Python solution
Use Pandas. Filter with df[df['description'].str.contains(r'\bSN\d{4}-\d{4}\b', regex=True)] and then sort with sort_values('product_id')[['product_id', 'product_name']]. The regex pattern enforces the four-digit, hyphen, four-digit format and the token boundaries.
Is Find Products with Valid Serial Numbers easy or hard?
It is an Easy problem with a 28.5% acceptance rate. The logic is one regex pattern, but most rejected submissions miss the word boundary requirement. Get the boundaries right and the solution is short.
How to solve Find Products with Valid Serial Numbers in O(n)?
Treat O(n) as O(n) in the number of rows with a constant-time pattern check per row. Since descriptions have bounded length in practice, a single regex pass per row is effectively linear in the number of products. Apply the pattern \bSN[0-9]{4}-[0-9]{4}\b to each description and keep the matching rows.
What is the best approach for Find Products with Valid Serial Numbers?
The best approach is regex matching with the pattern \bSN[0-9]{4}-[0-9]{4}\b. The word boundary anchors ensure the serial number is a standalone token. Use REGEXP in MySQL or str.contains in Pandas, then order the results by product_id. The time complexity is O(n * L), where n is the number of rows and L is the average description length.
What data structure is used in Find Products with Valid Serial Numbers?
No dedicated data structure is required. The problem operates on a relational table and uses string pattern matching on the description column. A regex engine or a manual character scan handles the matching logic.
What is the time complexity of Find Products with Valid Serial Numbers?
The time complexity is O(n * L), where n is the number of products and L is the average length of the description. Each description is scanned once by the regex engine. The extra space is O(1) per row, excluding the output.
Is Find Products with Valid Serial Numbers asked at Google, Amazon, or Meta?
FleetCode does not list company-specific tags for this problem. It is tagged as a Database problem at Easy difficulty with a 28.5% acceptance rate. Regex-based filtering questions like this appear in data-focused interview rounds, so practice the pattern with word boundaries.