1291. Sequential Digits

Enumeration
String
Math

TIME

O(1) (36 fixed candidates)

SPACE

O(1)

Intuition

Every number with sequential digits is a contiguous run from the string "123456789" e.g. 2345 is the substring "2345". Digits never wrap past 9, so there are very few such numbers (36 in total across lengths 2 to 9). Just generate them all and filter.

Approach

For each window length L from 2 to 9:
- For each start index i with i + L <= 9, take "123456789"[i : i+L] and convert to an integer.
- Keep it if it lies in [low, high].
Collect and sort the results (generating by increasing length then left-to-right already yields ascending order, but sorting is safe and trivial).

Complexity

Time: O(1), a fixed 36 candidates, independent of the range size
Space: O(1), bounded output

Edge Cases

No sequential-digit number in range → empty list
low == high and it's itself sequential → single element
Digits stop at 9 (no "...910"), which the substring approach enforces automatically
Results are naturally ascending by (length, start), matching the required sorted order

Code

from typing import List


class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        """
        1291. Sequential Digits
        Time: O(1)  (36 fixed candidates)
        Space: O(1)
        """
        digits = "123456789"
        result = []
        for length in range(2, 10):
            for i in range(0, 10 - length):
                num = int(digits[i:i + length])
                if low <= num <= high:
                    result.append(num)
        result.sort()
        return result

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 1291. Sequential Digits
 * Time: O(1)  (36 fixed candidates)
 * Space: O(1)
 */
class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        String digits = "123456789";
        List<Integer> result = new ArrayList<>();
        for (int length = 2; length <= 9; length++) {
            for (int i = 0; i + length <= 9; i++) {
                int num = Integer.parseInt(digits.substring(i, i + length));
                if (num >= low && num <= high) {
                    result.add(num);
                }
            }
        }
        Collections.sort(result);
        return result;
    }
}