Domain 2MediumMEDIUM

Sequential Digits

Generate all valid sequential digit numbers by iterating lengths and starting digits, then filter those within the [low, high] range.

Domain: medium•Updated: 2026-09-14
#Math#Simulation

Problem Breakdown

We need to identify integers within a specific inclusive range [low, high] where the digits form an ascending sequence (e.g., 123, 456).

  • Inputs: Two integers low and high. Constraints: 10≤low≤high≤10910 \le low \le high \le 10^9.
  • Output: A list of valid sequential integers, sorted in ascending order.
  • Implicit Constraints: Digits must be strictly increasing by exactly one (di+1=di+1d_{i+1} = d_i + 1). Leading zeros are not allowed (standard integer representation). The maximum digit is 9, which limits the length of any such number to at most 9 digits (123456789).
  • Edge Cases:
    • Range where no sequential numbers exist.
    • low and high boundaries matching valid sequences exactly.
    • Maximum possible value (10910^9) which has more digits than any valid sequence can support (since max digit is 9).

Intuition

A brute-force approach would iterate through every integer from low to high, checking if it satisfies the sequential property for each number.

  • Brute Force Complexity: O(high−low)O(high - low). Since high can be up to 10910^9, this is effectively O(109)O(10^9), which will time out (TLE).
  • Key Insight: Sequential numbers are extremely sparse and structurally constrained. They are defined entirely by their starting digit and length.
    • A number’s validity depends on its digits being consecutive integers ending at 9 or less.
    • This means we can generate all possible valid sequential numbers directly rather than checking every integer in the range.
  • Optimization: Since there is a maximum limit to how many such numbers exist (bounded by digit length and value of high), generating them allows us to filter for the [low, high] constraint efficiently.

Approach

  1. Determine Length Bounds: Valid sequential integers have lengths between 2 digits (10) up to a maximum determined by the constraints (99 digits). We iterate through possible lengths L.

    • Optimization: The minimum length is derived from low (number of digits in low). However, since we filter by value anyway, iterating all valid lengths 2-9 and filtering works. To be precise with complexity relative to input size: Iterate length from the number of digits in low up to the number of digits in high.
    • Correction: Actually, a shorter sequential number might exist within [low, high] only if it is ≥low\ge low. If we iterate lengths starting from 2, any generated number <low< low will be filtered out. Iterating length based on string length of inputs avoids unnecessary checks but given the small constant space (max digits), iterating fixed range 2..9 is cleaner and still optimal (O(1)O(1) effectively).
    • Refined Approach: Iterate lengths from 2 to 9 (since max digit constraint limits us here). For each length, iterate starting digits. Construct number mathematically or via string join. Check if within [low, high].
  2. Generation Logic:

    • Outer loop: Length L from 2 up to the maximum possible valid length for high (or just fixed max of 9 given constraints).
    • Inner loop: Starting digit S from 1 upwards such that all digits ≤9\le 9. Specifically, S+L−1≤9S + L - 1 \le 9, so SS goes up to 10−L10 - L.
    • Construct the number. If it falls within [low, high], add to result list.
  3. Sorting: Since we iterate length (increasing magnitude) and then starting digit (increasing value for same length), the generated numbers naturally appear in sorted order. We can return immediately without an explicit sort step.

Complexity Analysis

  • Time Complexity: O(1)O(1) relative to input values, or more precisely proportional to the number of valid sequential digits found (KK). Since max digit is 9 and length ≤9\le 9, there are at most roughly 45 such numbers total in existence up to 10910^9. We perform a constant amount of work.
  • Space Complexity: O(1)O(1) auxiliary space (excluding the output list storage), as we only store pointers or temporary variables for generation.

Solution

from typing import List

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []
        
        # Iterate over possible lengths of numbers (2 to 9 digits max due to digit constraint)
        for length in range(2, 10): 
            # For each length, iterate starting digit.
            # Max start digit is such that last digit <= 9 => start + length - 1 <= 9
            for start_digit in range(1, 10 - length + 1):
                num = int("".join(str(start_digit + i) for i in range(length)))
                
                if low <= num <= high:
                    res.append(num)
        
        return res

Edge Cases Handled

  • Range Boundaries: The if condition strictly checks [low, high], ensuring numbers outside the bounds (even valid sequential ones like 123456789 if high is smaller) are excluded.
  • No Valid Numbers: If no generated number falls in range, returns empty list naturally.
  • Max Constraints: The loop limit for length stops at 9 because a sequence of digits cannot exceed digit ‘9’ (e.g., starting with 1 and going to 10 is invalid). This handles the high≤109high \le 10^9 constraint implicitly without overflow issues in Python.
  • Sorted Output: The generation order guarantees sorted output, avoiding an unnecessary sort operation (O(Klog⁡K)O(K \log K)) where KK is small constant.