LeetCode 1291 - Sequential Digits

The problem asks us to find all integers within a given range [low, high] whose digits are sequential, meaning that each

leetcodemediumenumeration

LeetCode Problem 1291

Difficulty: 🟡 Medium
Topics: Enumeration

Solution

Problem Understanding

The problem asks us to find all integers within a given range [low, high] whose digits are sequential, meaning that each digit is exactly one greater than the previous digit. For instance, 123 is sequential because 2 = 1 + 1 and 3 = 2 + 1, but 135 is not sequential because the digits do not increase consecutively.

The input consists of two integers, low and high, which define the inclusive range in which we need to find such numbers. The output is a sorted list of integers that satisfy the sequential property within this range.

The constraints indicate that low and high are both at least 10 and at most 10^9. This upper bound rules out brute-force enumeration of all integers, because iterating from 10 to 10^9 would be far too slow. We need a method that generates only the sequential numbers without checking every integer in the range.

Important edge cases include numbers at the boundaries, such as low itself or high itself being sequential. Additionally, we need to consider numbers with different lengths (number of digits), because a 2-digit sequential number is valid, but 1-digit numbers are below the minimum constraint.

Approaches

The brute-force approach is straightforward: iterate over every integer in [low, high] and check if its digits are sequential. This is correct, but extremely inefficient because the range could contain up to a billion numbers. Checking every number is unnecessary since sequential digits form a very sparse set within the range.

The optimal approach leverages the fact that sequential digits are highly structured. All sequential numbers can be generated by starting with digits 1 through 9 and repeatedly appending the next consecutive digit until we exceed the maximum allowed number of digits or the value exceeds high. By systematically generating sequences this way, we avoid iterating over the vast majority of numbers that could never be sequential.

Approach Time Complexity Space Complexity Notes
Brute Force O(high - low) O(1) Iterates over every number and checks if sequential
Optimal O(1) with respect to range size O(1) extra Generates sequential numbers systematically; the total number of sequential numbers is bounded by the number of digits (constant)

Algorithm Walkthrough

  1. Initialize a list result to store sequential numbers.
  2. Iterate over starting digits from 1 to 9.
  3. For each starting digit, build numbers by repeatedly appending the next consecutive digit until the number exceeds high or the last digit becomes 9.
  4. After generating a number, check if it is within [low, high]. If it is, add it to the result list.
  5. Continue this process for all starting digits to generate all sequential numbers.
  6. Finally, sort the result list to ensure ascending order before returning it.

Why it works: This algorithm works because every sequential number is determined entirely by its starting digit and length. By systematically generating all sequences starting from each digit, we are guaranteed to produce every possible sequential number within the range without producing any invalid numbers.

Python Solution

from typing import List

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        result = []
        for start in range(1, 10):
            num = start
            next_digit = start
            while next_digit < 10:
                if low <= num <= high:
                    result.append(num)
                next_digit += 1
                num = num * 10 + next_digit
        return sorted(result)

The Python implementation follows the algorithm closely. We iterate over starting digits 1 through 9 and build numbers sequentially by appending digits. Each time we append, we check if the number falls in the range [low, high]. Finally, we sort the list because numbers generated from smaller starting digits may not automatically be in ascending order.

Go Solution

func sequentialDigits(low int, high int) []int {
    var result []int
    for start := 1; start <= 9; start++ {
        num := start
        nextDigit := start
        for nextDigit < 10 {
            if num >= low && num <= high {
                result = append(result, num)
            }
            nextDigit++
            num = num*10 + nextDigit
        }
    }
    // Sort the slice in ascending order
    for i := 0; i < len(result)-1; i++ {
        for j := i + 1; j < len(result); j++ {
            if result[i] > result[j] {
                result[i], result[j] = result[j], result[i]
            }
        }
    }
    return result
}

In Go, we follow the same logic. Go does not have a built-in sorted function for slices of integers, so we use a nested loop for sorting. Otherwise, the generation of sequential numbers is identical to the Python approach.

Worked Examples

Example 1: low = 100, high = 300

start num generation in range? added to result
1 1 -> 12 -> 123 yes 123
2 2 -> 23 -> 234 yes 234
3 3 -> 34 -> 345 no -
4-9 ... all exceed 300 -

Output: [123, 234]

Example 2: low = 1000, high = 13000

start num generation in range? added to result
1 1 -> 12 -> 123 -> 1234 -> 12345 1234, 12345 1234, 12345
2 2 -> 23 -> 234 -> 2345 -> 23456 2345 2345
3 3 -> 34 -> 345 -> 3456 3456 3456
4 4 -> 45 -> 456 -> 4567 4567 4567
5 ... 5678 5678
6 ... 6789 6789
7+ exceed 13000 - -

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

Complexity Analysis

Measure Complexity Explanation
Time O(1) The number of sequential numbers is bounded by 36 (all sequences from 1 to 9), so generation and sorting is effectively constant
Space O(1) The result list contains at most 36 numbers, so additional space is constant

Even though the algorithm contains loops, the total number of sequential numbers is extremely small and independent of the size of low and high.

Test Cases

# test cases
solution = Solution()

assert solution.sequentialDigits(100, 300) == [123, 234]  # basic example
assert solution.sequentialDigits(1000, 13000) == [1234, 2345, 3456, 4567, 5678, 6789, 12345]  # larger range
assert solution.sequentialDigits(10, 99) == [12, 23, 34, 45, 56, 67, 78, 89]  # 2-digit numbers only
assert solution.sequentialDigits(10, 12) == [12]  # minimal range with a single valid number
assert solution.sequentialDigits(90, 100) == []  # no numbers in range
assert solution.sequentialDigits(1, 9) == []  # all numbers below 10
assert solution.sequentialDigits(123456789, 987654321) == [123456789]  # very large range, only one valid number
Test Why
[100, 300] Simple 3-digit range, confirms basic functionality
[1000, 13000] Checks multi-digit generation and sorting
[10, 99] Tests 2-digit sequential numbers
[10, 12] Minimal range with a single valid sequential number
[90, 100] Range with no valid numbers
[1, 9] Below minimum sequential number size
[123456789, 987654321] Large range with only one valid number

Edge Cases

Edge Case 1: Range below 10, e.g., [1, 9]. Since sequential digits must have at least 2 digits, the algorithm correctly returns an empty list.

Edge Case 2: Range overlaps only partially with valid numbers, e.g., [90, 100]. No sequential numbers exist, but the algorithm still generates sequences and filters by range, returning an empty result.

Edge Case 3: Very large numbers near the upper constraint, e.g., [123456789, 987654321]. The algorithm correctly handles these by generating sequences up to the maximum number of digits possible and includes only valid numbers within the given range. There is no integer