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
lowandhigh. Constraints: . - Output: A list of valid sequential integers, sorted in ascending order.
- Implicit Constraints: Digits must be strictly increasing by exactly one (). 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.
lowandhighboundaries matching valid sequences exactly.- Maximum possible value () 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: . Since
highcan be up to , this is effectively , 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
-
Determine Length Bounds: Valid sequential integers have lengths between 2 digits (
10) up to a maximum determined by the constraints ( digits). We iterate through possible lengthsL.- Optimization: The minimum length is derived from
low(number of digits inlow). 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 inlowup to the number of digits inhigh. - Correction: Actually, a shorter sequential number might exist within
[low, high]only if it is . If we iterate lengths starting from 2, any generated number 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 range2..9is cleaner and still optimal ( 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].
- Optimization: The minimum length is derived from
-
Generation Logic:
- Outer loop: Length
Lfrom 2 up to the maximum possible valid length forhigh(or just fixed max of 9 given constraints). - Inner loop: Starting digit
Sfrom 1 upwards such that all digits . Specifically, , so goes up to . - Construct the number. If it falls within
[low, high], add to result list.
- Outer loop: Length
-
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: relative to input values, or more precisely proportional to the number of valid sequential digits found (). Since max digit is 9 and length , there are at most roughly 45 such numbers total in existence up to . We perform a constant amount of work.
- Space Complexity: 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
ifcondition strictly checks[low, high], ensuring numbers outside the bounds (even valid sequential ones like 123456789 ifhighis 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 constraint implicitly without overflow issues in Python.
- Sorted Output: The generation order guarantees sorted output, avoiding an unnecessary sort operation () where is small constant.