LeetCode 3415 - Find Products with Three Consecutive Digits

LeetCode Problem 3415

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This is a SQL database problem involving pattern matching on strings.

We are given a table named Products with two columns:

Column	Description
product_id	Unique identifier for each product
name	Product name string

The goal is to return all products whose names contain a sequence of exactly three consecutive digits.

The important detail is the word exactly. A product name should be included only if it contains a run of three digits that is not part of a longer digit sequence.

Consider the examples:

• "ABC123XYZ" contains "123" surrounded by non-digits, so it qualifies.
• "789Product" starts with exactly three digits, so it qualifies.
• "Item003Description" contains "003" and qualifies.
• "Product56789" contains five consecutive digits, not exactly three, so it does not qualify.
• "A12B34C" only contains runs of length two, so it does not qualify.

In other words, we are looking for a substring matching:

• three consecutive digits [0-9]{3}
• immediately before the sequence is either the beginning of the string or a non-digit
• immediately after the sequence is either the end of the string or a non-digit

A naive interpretation might incorrectly match the "567" portion inside "56789", but that would be wrong because those digits belong to a longer run of digits.

Since this is a database problem, the intended solution is to use a regular expression that identifies exactly three consecutive digits and excludes longer digit runs.

Important Edge Cases

A few cases can easily cause mistakes:

• Three digits at the beginning of the string, such as "123ABC".
• Three digits at the end of the string, such as "ABC123".
• Three digits surrounded by letters, such as "ABC123XYZ".
• Longer digit runs, such as "ABC1234XYZ", which should not match.
• Multiple valid three-digit groups, such as "ABC123XYZ456", which should still be returned once.
• Leading zeros, such as "Item003Description", which are still valid digits.

Approaches

Brute Force Approach

A brute force approach would examine every product name character by character and identify every contiguous run of digits.

For each run:

• Determine its length.
• Check whether the length is exactly three.
• If at least one such run exists, include the product in the result.

This approach is correct because it explicitly measures every digit sequence and verifies the exact length requirement.

However, implementing character-by-character scanning inside SQL is cumbersome and unnecessary. Database systems already provide efficient regular expression functionality that can express this condition directly.

Key Insight

The key observation is that this problem is fundamentally a pattern-matching task.

We need a digit sequence of length three that is not connected to additional digits on either side. A regular expression can describe this precisely:

(^|[^0-9])[0-9]{3}([^0-9]|$)

This pattern ensures:

• Before the three digits is either the start of the string or a non-digit.
• Exactly three digits appear.
• After the three digits is either a non-digit or the end of the string.

Using a regex allows the database engine to perform the matching directly without manually parsing each string.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × L)	O(1)	Scan every character of every product name
Optimal	O(N × L)	O(1)	Use regex pattern matching directly in SQL

Where:

• N = number of rows
• L = average product name length

Although the asymptotic complexity is similar, the regex solution is significantly cleaner and is the intended database solution.

Algorithm Walkthrough

Optimal Algorithm

1. Read each row from the Products table.
2. For every product name, apply a regular expression search.
3. Use a regex that looks for exactly three consecutive digits:

(^|[^0-9])[0-9]{3}([^0-9]|$)

4. If the regex matches, keep that row in the result set.
5. If the regex does not match, discard the row.
6. Sort the remaining rows by product_id in ascending order.
7. Return the resulting table.

Why it works

The regex guarantees that the three-digit sequence is isolated from any additional digits. The left boundary requires either the start of the string or a non-digit character, and the right boundary requires either a non-digit character or the end of the string. Therefore any matched digit run must have length exactly three, which is precisely the condition required by the problem.

Python Solution

This is a Database problem, so LeetCode expects an SQL query rather than a Python implementation. For completeness, the equivalent logic in Python would be:

import re
from typing import List

class Solution:
    def findProducts(self, products: List[tuple[int, str]]) -> List[tuple[int, str]]:
        pattern = re.compile(r'(^|[^0-9])[0-9]{3}([^0-9]|$)')

        result = []

        for product_id, name in products:
            if pattern.search(name):
                result.append((product_id, name))

        result.sort(key=lambda x: x[0])
        return result

The implementation first compiles the regular expression. It then scans every product name and checks whether the pattern exists. Any matching row is added to the result list. Finally, the list is sorted by product_id to satisfy the ordering requirement.

Go Solution

Again, the actual LeetCode submission is SQL, but the equivalent Go implementation would be:

The problem asks us to query a database table of products and find those whose names contain exactly three consecutive digits in a row. The table Products has two columns: product_id, which uniquely identifies each product, and name, which contains the product name as a string.

In simpler terms, we are searching for products like ABC123XYZ where a substring of the name is exactly three digits long, such as 123. Importantly, sequences longer than three digits, such as 56789 in Product56789, should not be included, because the problem specifies "exactly three consecutive digits". The results must be sorted by product_id in ascending order.

The problem implies several constraints and clarifications:

• Names may contain letters, numbers, or symbols.
• Names could contain multiple sequences of digits, but we only care about sequences that are exactly three digits long.
• The database may be large, so solutions that scan every substring inefficiently could be slow.

Key edge cases to consider include:

• Names with no digits.
• Names with sequences of digits shorter or longer than three.
• Names that contain multiple valid three-digit sequences.
• Products with consecutive product_id gaps or very large IDs.

Approaches

A brute-force approach would be to iterate over each product, and for each product name, check every possible substring of length three to see if it contains only digits. This approach is correct because it explicitly checks all possibilities. However, it becomes inefficient for large tables with long product names, because it requires a full scan of every character in every name.

The optimal approach leverages SQL string pattern matching using the REGEXP operator (or REGEXP_LIKE in some dialects). We can construct a regular expression that matches exactly three consecutive digits, ensuring that they are not part of a longer sequence. The key observation is that SQL allows us to detect patterns like [0-9]{3} with boundaries or negative lookahead/lookbehind to enforce the "exactly three" rule. This avoids scanning each substring manually and delegates the work to the database engine, which is highly optimized for such operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Iterate over each product name and each substring of length 3; n = # of products, m = max length of name
Optimal	O(n)	O(1)	Use SQL REGEXP to match exactly three consecutive digits, letting DB handle string search efficiently

Algorithm Walkthrough

1. Access the Products table and select the columns product_id and name for output.
2. Construct a regular expression pattern that matches exactly three consecutive digits. The pattern should ensure that the three digits are not preceded or followed by another digit.
3. Use the WHERE clause with REGEXP to filter rows whose name matches the pattern.
4. Order the results by product_id in ascending order.

Why it works: The regular expression captures all valid three-digit sequences while excluding sequences of length two or longer than three. By letting the database engine handle the pattern matching, we avoid manually scanning each string. The ORDER BY clause guarantees the results are returned in the correct order.

Python Solution

import sqlite3
from typing import List, Tuple

def find_products_with_three_digits(connection: sqlite3.Connection) -> List[Tuple[int, str]]:
    query = """
    SELECT product_id, name
    FROM Products
    WHERE name REGEXP '(^|[^0-9])[0-9]{3}([^0-9]|$)'
    ORDER BY product_id ASC;
    """
    # sqlite does not support REGEXP natively, we can create a custom function if needed
    connection.create_function("REGEXP", 2, lambda pattern, value: 1 if re.search(pattern, value) else 0)
    
    cursor = connection.cursor()
    cursor.execute(query)
    results = cursor.fetchall()
    cursor.close()
    return results

The Python implementation relies on SQLite, which does not natively support REGEXP. Therefore, we create a custom function REGEXP using Python's re.search to allow regex matching. The query selects product_id and name from Products where the name contains exactly three consecutive digits, ensuring sequences of other lengths are ignored. Finally, results are ordered by product_id.

Go Solution

package main

import (
	"regexp"
	"sort"
)

type Product struct {
	ProductID int
	Name      string
}

func findProducts(products []Product) []Product {
	pattern := regexp.MustCompile(`(^|[^0-9])[0-9]{3}([^0-9]|$)`)

	result := make([]Product, 0)

	for _, product := range products {
		if pattern.MatchString(product.Name) {
			result = append(result, product)
		}
	}

	sort.Slice(result, func(i, j int) bool {
		return result[i].ProductID < result[j].ProductID
	})

	return result
}

The Go version uses the standard regexp package. The logic is identical to the Python implementation. Go slices automatically grow as matching products are appended. No special handling for integer overflow or nil values is required because the problem only involves string pattern matching and sorting.

SQL Solution

SELECT product_id, name
FROM Products
WHERE name REGEXP '(^|[^0-9])[0-9]{3}([^0-9]|$)'
ORDER BY product_id;

This query directly filters rows whose names contain a sequence of exactly three consecutive digits and then orders the result by product_id in ascending order.

Worked Examples

Example 1: ABC123XYZ

Check	Value
Product Name	ABC123XYZ
Matching Run	123
Left Character	C (non-digit)
Right Character	X (non-digit)
Valid?	Yes

The regex successfully matches the substring "123".

Result: Included.

Example 2: A12B34C

Check	Value
Digit Runs	12, 34
Lengths	2, 2
Any Length 3 Run?	No
Valid?	No

Result: Excluded.

Example 3: Product56789

Check	Value
Digit Run	56789
Length	5
Exactly 3 Digits?	No
Valid?	No

Although "567" exists inside the string, it is part of a larger digit run.

Result: Excluded.

Example 4: NoDigitsHere

Check	Value
Digit Runs	None
Valid?	No

Result: Excluded.

Example 5: 789Product

Check	Value
Matching Run	789
Left Boundary	Start of string
Right Character	P (non-digit)
Valid?	Yes

Result: Included.

Example 6: Item003Description

Check	Value
Matching Run	003
Left Character	m (non-digit)
Right Character	D (non-digit)
Valid?	Yes

Leading zeros are allowed.

Result: Included.

Example 7: Product12X34

Check	Value
Digit Runs	12, 34
Lengths	2, 2
Valid?	No

Result: Excluded. "database/sql" "regexp" )

func FindProductsWithThreeDigits(db *sql.DB) ([][2]interface{}, error) { rows, err := db.Query("SELECT product_id, name FROM Products") if err != nil { return nil, err } defer rows.Close()

pattern := regexp.MustCompile(`(^|[^0-9])[0-9]{3}([^0-9]|$)`)
var results [][2]interface{}

for rows.Next() {
    var id int
    var name string
    if err := rows.Scan(&id, &name); err != nil {
        return nil, err
    }
    if pattern.MatchString(name) {
        results = append(results, [2]interface{}{id, name})
    }
}
return results, nil

}

In Go, since standard SQL drivers do not universally support regex in queries, we fetch all products and use Go's `regexp` package to filter names. The logic mirrors the Python solution but handles row scanning and type conversion explicitly. Slices are used to store results, and the regex ensures only exactly three consecutive digits are matched.

## Worked Examples

For the input:

+-------------+--------------------+ | product_id | name | +-------------+--------------------+ | 1 | ABC123XYZ | | 2 | A12B34C | | 3 | Product56789 | | 4 | NoDigitsHere | | 5 | 789Product | | 6 | Item003Description | | 7 | Product12X34 | +-------------+--------------------+

Step by step:

1. Product 1: `ABC123XYZ` contains `123`, matches pattern.
2. Product 2: `A12B34C` has `12` and `34`, neither exactly three digits, skip.
3. Product 3: `Product56789` has `56789`, too long, skip.
4. Product 4: `NoDigitsHere` has no digits, skip.
5. Product 5: `789Product` contains `789`, matches pattern.
6. Product 6: `Item003Description` contains `003`, matches pattern.
7. Product 7: `Product12X34` sequences are `12` and `34`, skip.

Output after ordering by `product_id`:

+-------------+--------------------+ | product_id | name | +-------------+--------------------+ | 1 | ABC123XYZ | | 5 | 789Product | | 6 | Item003Description | +-------------+--------------------+

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(N × L) | Each product name may be scanned once by the regex engine |
| Space | O(1) | Only the regex pattern and a small amount of auxiliary memory are used |

The database engine evaluates the regular expression against each product name. In the worst case, every character in every name may be inspected, giving a complexity proportional to the total input size. No additional data structures that grow with the input are required.

## Test Cases

```python
import re

pattern = re.compile(r'(^|[^0-9])[0-9]{3}([^0-9]|$)')

assert bool(pattern.search("ABC123XYZ")) is True      # standard valid case
assert bool(pattern.search("789Product")) is True     # digits at beginning
assert bool(pattern.search("Item003Description")) is True  # leading zeros
assert bool(pattern.search("ABC123")) is True         # digits at end
assert bool(pattern.search("123ABC")) is True         # digits at start

assert bool(pattern.search("A12B34C")) is False       # only length-2 runs
assert bool(pattern.search("Product56789")) is False  # run longer than 3
assert bool(pattern.search("1234")) is False          # exactly 4 digits
assert bool(pattern.search("12")) is False            # fewer than 3 digits
assert bool(pattern.search("NoDigitsHere")) is False  # no digits

assert bool(pattern.search("ABC123XYZ456")) is True   # multiple valid runs
assert bool(pattern.search("A1234B5678C")) is False   # only longer runs
assert bool(pattern.search("X999Y")) is True          # exactly three digits
assert bool(pattern.search("999")) is True            # entire string is 3 digits
assert bool(pattern.search("9999")) is False          # entire string is 4 digits

Test Summary

Test	Why
ABC123XYZ	Standard valid example
789Product	Three digits at beginning
Item003Description	Leading zeros
ABC123	Three digits at end
123ABC	Boundary condition at start
A12B34C	No run of length three
Product56789	Longer digit sequence
1234	Four consecutive digits
12	Too few digits
NoDigitsHere	No digits present
ABC123XYZ456	Multiple valid groups
A1234B5678C	Only invalid long groups
X999Y	Exactly three digits in middle
999	Entire string is valid run
9999	Entire string is invalid run

Edge Cases

Three Digits at the Beginning or End of the String

A common bug is forgetting that a valid three-digit sequence may appear at the start or end of the product name. For example, "789Product" and "ABC123" should both match. The regex handles this through the ^ and $ anchors, which explicitly allow string boundaries to act as valid neighbors.

Longer Digit Sequences

The most important edge case is a sequence like "Product56789". A careless implementation might find the substring "567" and incorrectly accept the row. The regex prevents this by requiring that the character after the third digit be either a non-digit or the end of the string. Since another digit follows "567", the match fails.

Leading Zeros

Some implementations accidentally treat digit sequences as numbers and remove leading zeros. The product name "Item003Description" contains the valid sequence "003". Because the solution treats the name as a string and performs pattern matching rather than numeric conversion, leading zeros remain intact and are matched correctly.

Multiple Digit Groups

A product name may contain several digit groups. For example, "ABC123XYZ456" contains two separate valid runs. The problem only requires determining whether at least one valid run exists. The regex search succeeds as soon as one qualifying sequence is found, and the row is correctly included exactly once.

Names Without Any Digits

Strings such as "NoDigitsHere" contain no numeric characters. The regex cannot match, so the row is excluded. This ensures that only products containing a qualifying three-digit sequence appear in the result. | Time | O(n * m) | n = number of products, m = average name length; regex is applied per name | | Space | O(n) | storing results of matching products |

Although regex matching scans each string, this is far more efficient than checking all substrings manually, and database engines optimize regex evaluation internally.

Test Cases

# provided examples
assert find_products_with_three_digits(conn) == [(1, "ABC123XYZ"), (5, "789Product"), (6, "Item003Description")]

# edge cases
assert find_products_with_three_digits(conn) == []  # no products
assert find_products_with_three_digits(conn) == [(10, "000Product")]  # sequence at start
assert find_products_with_three_digits(conn) == [(11, "Product999")]  # sequence at end
assert find_products_with_three_digits(conn) == [(12, "A123B456C")]  # multiple sequences, all valid
assert find_products_with_three_digits(conn) == []  # sequences longer than three digits ignored

Test	Why
Provided example	Validates standard case with mixed valid/invalid sequences
No products	Tests empty table handling
Sequence at start	Tests boundary condition at string start
Sequence at end	Tests boundary condition at string end
Multiple sequences	Ensures multiple three-digit sequences are detected
Longer sequences	Ensures sequences longer than three are ignored

Edge Cases

1. Names without any digits: Some product names may contain letters or symbols only. A naive implementation that assumes a digit exists could fail. The regex ensures these names simply do not match.
2. Sequences longer than three digits: For instance, Product12345 contains five digits in a row. The solution must exclude this, which is handled by checking that digits are not immediately preceded or followed by another digit.
3. Sequences at string boundaries: Products like 123Start or End456 test the handling of string edges. Using (^|[^0-9]) and ([^0-9]|$) in the regex ensures these sequences are detected correctly at the beginning or end of the name.

This implementation ensures correctness for standard inputs, edge cases, and respects the "exactly three digits" constraint efficiently.