#1291

Medium

auto_awesomeEnumeration-driven solution strategy

LeetCode Problem Workspace

Sequential Digits

Find all integers within a range whose digits form a strictly increasing consecutive sequence using enumeration techniques.

enumeration

Problem Statement

A number has sequential digits if each digit is exactly one greater than the previous digit. Given two integers low and high, identify all numbers between them, inclusive, that satisfy this property.

Return the list of sequential digit numbers sorted in ascending order. For example, with low = 100 and high = 300, the result is [123,234]. Ensure your solution efficiently enumerates valid numbers rather than testing each integer individually.

Examples

Example 1

Input: low = 100, high = 300

Output: [123,234]

Example details omitted.

Example 2

Input: low = 1000, high = 13000

Output: [1234,2345,3456,4567,5678,6789,12345]

Example details omitted.

Constraints

10 <= low <= high <= 10^9

Solution Approach

Generate Numbers by Digit Length

Determine the number of digits for low and high. For each digit length, build numbers starting from 1 to 9, appending consecutive digits until the number length matches. This avoids unnecessary checks outside the target range.

Filter Within Range

After generating each sequential number, immediately check if it falls between low and high. Only include numbers that satisfy the range constraints to maintain efficiency and prevent storing invalid candidates.

Return Sorted List

Because numbers are generated in increasing order from the smallest starting digit, simply collect valid numbers into a list. The resulting array is inherently sorted, matching the problem requirement without additional sorting steps.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) in practice since the total sequential numbers are limited by digit count (1-9), even with high up to 10^9. Space complexity is O(1) extra beyond the output list, as numbers are generated on the fly and stored only if they fall in range.

What Interviewers Usually Probe

Focuses on generating numbers without testing every integer individually.
Expects you to recognize the sequential digit pattern quickly.
Checks for efficiency by restricting generation to relevant digit lengths.

Common Pitfalls or Variants

Common pitfalls

Attempting to iterate every integer from low to high, which is inefficient.
Forgetting to handle different digit lengths separately, leading to missed numbers.
Not maintaining ascending order, causing additional unnecessary sorting.

Follow-up variants

Return sequential digits in descending order instead of ascending.
Count the number of sequential digit numbers within a range instead of listing them.
Find the next sequential digit number greater than a given value.

FAQ

What is a sequential digit number?

A number where each digit is exactly one greater than the previous digit, such as 123 or 6789.

How do you efficiently generate sequential digits within a range?

Build numbers by appending consecutive digits based on length and starting digit, then filter by the given low and high values.

Can this approach handle large ranges like up to 10^9?

Yes, because sequential numbers are limited by digit count, generation remains efficient regardless of range size.

Do I need to sort the output after generating numbers?

No, generating numbers from smallest starting digit to largest inherently produces a sorted list.

Which algorithm pattern is most relevant for Sequential Digits?

Enumeration-driven solution strategy is key, focusing on generating valid numbers directly rather than checking each candidate.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        ans = []
        for i in range(1, 9):
            x = i
            for j in range(i + 1, 10):
                x = x * 10 + j
                if low <= x <= high:
                    ans.append(x)
        return sorted(ans)

Continue Practicing

#1534 count good triplets #1566 detect pattern of length m repeated k or more times #1601 maximum number of achievable transfer requests