Problem Description

A number has sequential digits when each digit is exactly one more than the digit before it. For example, 123 has sequential digits (1→2→3), but 132 does not.

Given two integers low and high that define a range [low, high], find all integers within this range (inclusive) that have sequential digits. Return these numbers in a sorted list.

Examples of sequential digit numbers:

• 12 (1→2)
• 123 (1→2→3)
• 234 (2→3→4)
• 456789 (4→5→6→7→8→9)

Examples of non-sequential digit numbers:

• 120 (2 is followed by 0, not 3)
• 135 (3 is followed by 5, not 4)

The solution works by systematically generating all possible sequential digit numbers. It starts with each digit from 1 to 8 as the first digit, then keeps adding the next consecutive digit to form longer numbers. For instance, starting with 1, it creates 12, then 123, then 1234, and so on. Starting with 2, it creates 23, then 234, then 2345, and continues this pattern.

For each generated number, if it falls within the range [low, high], it's added to the result list. Finally, the list is sorted before returning.

Intuition

The key insight is recognizing that sequential digit numbers follow a very specific pattern - they can only start with digits 1 through 9, and once you pick a starting digit, the rest of the number is completely determined.

Think about it this way: if a number starts with 3, the only way it can have sequential digits is if it continues as 34, 345, 3456, and so on. There's no other possibility. This means there are actually very few sequential digit numbers in total.

Since sequential digit numbers are limited and predictable, we can generate all of them systematically rather than checking every number in the range. This is much more efficient than examining each number from low to high to see if it has sequential digits.

The generation process is straightforward:

• Pick a starting digit (1 through 9)
• Keep appending the next digit (current + 1) to build longer numbers
• Stop when we reach digit 9 or go beyond our range

For example, starting with 2:

• First number: 2
• Multiply by 10 and add 3: 23
• Multiply by 10 and add 4: 234
• Multiply by 10 and add 5: 2345
• Continue until we can't add more digits

This approach naturally generates all possible sequential digit numbers. We just need to filter out those outside our range and sort the final result. The beauty of this solution is that it only generates valid candidates instead of wasting time checking invalid numbers.

Solution Approach

The implementation uses a nested loop structure to generate all possible sequential digit numbers:

Outer Loop - Starting Digit Selection:

for i in range(1, 9):

We iterate through starting digits from 1 to 8. Note that we stop at 8 because 9 cannot be a starting digit for a sequential number (there's no digit 10 to follow it).

Inner Loop - Building Sequential Numbers:

x = i  # Initialize with starting digit
for j in range(i + 1, 10):
    x = x * 10 + j

For each starting digit i, we:

1. Initialize x with the starting digit
2. Iterate j from i+1 to 9 (the next sequential digits)
3. Build the number by multiplying the current value by 10 and adding the next digit

For example, when i = 2:

• Initially: x = 2
• When j = 3: x = 2 * 10 + 3 = 23
• When j = 4: x = 23 * 10 + 4 = 234
• When j = 5: x = 234 * 10 + 5 = 2345
• Continues until j = 9

Range Filtering:

if low <= x <= high:
    ans.append(x)

Each generated number is checked against the given range. Only numbers within [low, high] are added to the result list.

Final Sorting:

return sorted(ans)

The generated numbers aren't naturally in ascending order because we generate all numbers starting with 1, then all starting with 2, etc. For instance, 123 (starting with 1) would come before 23 (starting with 2) in our generation order. The sorted() function ensures the final output meets the requirement of being in ascending order.

Time Complexity: O(1) - We generate at most 36 sequential digit numbers (since there are only 36 possible sequential digit numbers total), regardless of the input range.

Space Complexity: O(1) - The result list can contain at most 36 numbers, which is constant.

Example Walkthrough

Let's walk through the solution with low = 100 and high = 300.

Step 1: Generate numbers starting with digit 1

• Start with x = 1
• Add digit 2: x = 1 * 10 + 2 = 12 (12 < 100, not in range)
• Add digit 3: x = 12 * 10 + 3 = 123 (100 ≤ 123 ≤ 300, add to result)
• Add digit 4: x = 123 * 10 + 4 = 1234 (1234 > 300, not in range)
• Continue building but all subsequent numbers (12345, 123456, etc.) will be > 300

Step 2: Generate numbers starting with digit 2

• Start with x = 2
• Add digit 3: x = 2 * 10 + 3 = 23 (23 < 100, not in range)
• Add digit 4: x = 23 * 10 + 4 = 234 (100 ≤ 234 ≤ 300, add to result)
• Add digit 5: x = 234 * 10 + 5 = 2345 (2345 > 300, not in range)
• All subsequent numbers will be > 300

Step 3: Generate numbers starting with digits 3-8

• Starting with 3: generates 3, 34, 345, 3456... (none in range [100, 300])
• Starting with 4: generates 4, 45, 456, 4567... (none in range)
• Starting with 5: generates 5, 56, 567, 5678... (none in range)
• Starting with 6: generates 6, 67, 678, 6789... (none in range)
• Starting with 7: generates 7, 78, 789, 78910 (invalid)... (none in range)
• Starting with 8: generates 8, 89, 8910 (invalid)... (none in range)

Step 4: Sort the results

• Current result list: [123, 234]
• After sorting: [123, 234] (already in order)

Final Answer: [123, 234]

This example demonstrates how the algorithm efficiently generates only valid sequential digit numbers and filters them by the given range, avoiding the need to check every number between 100 and 300.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm uses two nested loops:

• The outer loop runs from i = 1 to i = 8 (8 iterations)
• The inner loop runs from j = i + 1 to j = 9, which varies based on i

The total number of iterations across both loops is: (9-1) + (9-2) + (9-3) + ... + (9-8) = 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

This generates at most 36 sequential digit numbers. The sorting operation at the end sorts at most 36 elements, which takes O(36 log 36) = O(1) time.

Since the number of operations is constant and doesn't depend on the input values low and high, the time complexity is O(1).

Space Complexity: O(1)

The space used by the algorithm:

• The ans list stores at most 36 sequential digit numbers (all possible sequential digit numbers from 12 to 123456789)
• The variables i, j, and x use constant space

Since the maximum space used is bounded by a constant (36 elements in the worst case), the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Early Termination Optimization Gone Wrong

A common pitfall is trying to optimize by breaking out of loops early when numbers exceed the high limit:

Incorrect Implementation:

for start_digit in range(1, 9):
    current_number = start_digit
    for next_digit in range(start_digit + 1, 10):
        current_number = current_number * 10 + next_digit
        if current_number > high:
            break  # WRONG: This breaks the inner loop only
        if low <= current_number <= high:
            result.append(current_number)

The Problem: This approach seems logical but misses valid numbers. When we break from the inner loop, we move to the next starting digit. However, numbers with later starting digits can be smaller than numbers with earlier starting digits but more digits total.

Example: If high = 1000:

• Starting with 1: generates 12, 123, 1234 (breaks at 1234 > 1000)
• Starting with 2: generates 23, 234 (234 < 1000, valid!)
• We'd miss 234, 345, 456, 567, 678, 789 if we stopped processing entirely

2. Forgetting to Sort the Results

The generation order is NOT naturally sorted:

• First we generate: 12, 123, 1234, ... (all starting with 1)
• Then: 23, 234, 2345, ... (all starting with 2)
• Result: [12, 123, 1234, 23, 234, ...] - NOT sorted!

Solution: Always include return sorted(result) at the end.

3. Off-by-One Errors in Range Boundaries

Common Mistakes:

# Wrong: Includes 9 as a starting digit
for start_digit in range(1, 10):  # Should be range(1, 9)

# Wrong: Excludes 9 as a continuation digit
for next_digit in range(start_digit + 1, 9):  # Should be range(start_digit + 1, 10)

Starting digit must be 1-8 (not 9), but continuation digits can include 9.

4. Alternative Approach Pitfall: String Manipulation

Some might try using string operations:

# Tempting but inefficient approach
for i in range(1, 9):
    s = str(i)
    for j in range(i + 1, 10):
        s += str(j)
        num = int(s)
        if low <= num <= high:
            result.append(num)

Problems:

• String concatenation creates new strings each time (inefficient)
• Converting between string and integer repeatedly adds overhead
• The mathematical approach (x * 10 + j) is cleaner and faster

Recommended Solution Pattern:

def sequentialDigits(self, low: int, high: int) -> List[int]:
    result = []
  
    # Generate all possible sequential digit numbers
    for start in range(1, 9):
        num = start
        for next_digit in range(start + 1, 10):
            num = num * 10 + next_digit
            if low <= num <= high:
                result.append(num)
            # Don't break here! Continue generating
  
    # Critical: Sort before returning
    return sorted(result)

This avoids all the common pitfalls while maintaining the correct O(1) complexity.