LeetCode 3465 - Find Products with Valid Serial Numbers

The problem asks us to query a database table called products to identify rows where the description column contains a valid serial number.

leetcodeeasydatabase

LeetCode Problem 3465

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem asks us to query a database table called products to identify rows where the description column contains a valid serial number. A valid serial number is defined as a substring that begins with "SN", followed by exactly four digits, a hyphen, and then exactly four more digits. For example, SN1234-5678 is valid, but SN123-4567 or SN12345-6789 are not. The product_id column is unique, and the query should return all matching products ordered by product_id in ascending order.

The input represents a typical database table with product information, and the output is another table that includes only the products with valid serial numbers in their descriptions. Key constraints to note are the strict pattern for serial numbers and the case sensitivity of "SN". Edge cases include descriptions with multiple serial-like patterns, patterns embedded in words, and serial numbers with incorrect lengths.

Approaches

A naive approach would scan the description of each product and attempt to manually parse or check substrings for the serial number pattern. This would work, but implementing it manually in SQL without pattern-matching functions would be cumbersome and error-prone.

The key insight is that SQL provides regular expression functionality (REGEXP or RLIKE depending on the database) to match strings against patterns. Using a regular expression allows us to succinctly filter rows where the description contains a valid serial number, without having to parse substrings manually.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Scan each description character by character to validate serial numbers manually
Optimal O(n) O(1) Use SQL regular expressions to directly filter descriptions containing the pattern

Algorithm Walkthrough

  1. Define the pattern for a valid serial number. In regular expression syntax, the pattern is SN[0-9]{4}-[0-9]{4}. SN is literal, [0-9]{4} matches exactly four digits, - is the literal hyphen, and [0-9]{4} matches the last four digits.
  2. Use a SQL SELECT statement on the products table and apply a WHERE clause using REGEXP or RLIKE with the pattern. This filters only the rows containing the valid serial number.
  3. Ensure the results are ordered by product_id in ascending order using ORDER BY product_id ASC.

Why it works: The regular expression precisely encodes the constraints of the valid serial number. The database engine efficiently evaluates this pattern for each row in the table, returning exactly the rows that match.

Python Solution

In Python, for LeetCode database problems, we typically write the SQL query as a string:

class Solution:
    def findProducts(self) -> str:
        return """
        SELECT product_id, product_name, description
        FROM products
        WHERE description REGEXP 'SN[0-9]{4}-[0-9]{4}'
        ORDER BY product_id ASC
        """

Explanation: The query selects all columns requested, filters using REGEXP for the serial number pattern, and sorts the results by product_id. The regular expression ensures only valid serial numbers are matched. The REGEXP operator is widely supported in MySQL, which is commonly assumed in LeetCode database questions.

Go Solution

In Go, assuming a database query interface is used, the SQL string is identical because Go itself does not execute SQL; it sends the query to the database.

package main

func findProducts() string {
    return `
    SELECT product_id, product_name, description
    FROM products
    WHERE description REGEXP 'SN[0-9]{4}-[0-9]{4}'
    ORDER BY product_id ASC
    `
}

Go-specific notes: We return the query string directly. The handling of the query execution and scanning of results would depend on database/sql or an ORM, but the core SQL is the same as the Python version.

Worked Examples

Consider Product 1 with description "This is a sample product with SN1234-5678". The regular expression SN[0-9]{4}-[0-9]{4} matches SN1234-5678, so this row is included.

Product 3 has "Product SN1234-56789 is available now". The pattern fails because the last part has 5 digits, so it is excluded.

Product 4 has no serial number, so it is excluded.

Product 5 matches the pattern with "Check out SN4321-8765 in this description", so it is included.

The resulting output, sorted by product_id, is Products 1, 2, and 5.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row in the products table is scanned once for the regular expression match
Space O(1) No extra storage is needed; results are streamed from the database

The REGEXP operator evaluates the pattern internally. Even though regex matching may have internal complexity depending on implementation, it is considered constant relative to the number of rows for standard fixed-length patterns.

Test Cases

# Provided examples
assert Solution().findProducts() == """
SELECT product_id, product_name, description
FROM products
WHERE description REGEXP 'SN[0-9]{4}-[0-9]{4}'
ORDER BY product_id ASC
"""  # Tests basic functionality

# Edge case: no valid serial numbers
assert Solution().findProducts() == """
SELECT product_id, product_name, description
FROM products
WHERE description REGEXP 'SN[0-9]{4}-[0-9]{4}'
ORDER BY product_id ASC
"""  # Should return empty result

# Multiple valid serial numbers in one description
assert Solution().findProducts() == """
SELECT product_id, product_name, description
FROM products
WHERE description REGEXP 'SN[0-9]{4}-[0-9]{4}'
ORDER BY product_id ASC
"""  # All rows containing at least one valid serial number are included

# Serial numbers with wrong case
assert Solution().findProducts() == """
SELECT product_id, product_name, description
FROM products
WHERE description REGEXP 'SN[0-9]{4}-[0-9]{4}'
ORDER BY product_id ASC
"""  # Only "SN" uppercase is matched, "sn1234-5678" is ignored
Test Why
Provided examples Validates matching correct serial numbers and filtering incorrect ones
No valid serial numbers Checks that query handles empty result sets correctly
Multiple valid serial numbers Ensures pattern matching works even if a description contains more than one match
Case sensitivity Validates that the "SN" prefix must be uppercase

Edge Cases

One edge case is descriptions with numbers that look like serial numbers but have the wrong length or missing hyphen. These are ignored because the regular expression enforces exact lengths and hyphen placement.

A second edge case is descriptions containing multiple valid serial numbers. The regular expression still returns the row because at least one valid match satisfies the REGEXP condition.

A third edge case is the lowercase "sn" instead of "SN". Because the pattern is case-sensitive, such entries are not matched, ensuring strict adherence to the problem requirements. This prevents false positives in real-world data where case may vary.