class Solution:
def sequentialDigits(self, low: int, high: int) -> list[int]:
result = []
for length in range(len(str(low)), len(str(high)) + 1):
for start in range(1, 10 - length + 1):
num = 0
for i in range(length):
num = num * 10 + (start + i)
if low <= num <= high:
result.append(num)
result.sort()
return result
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> result;
for (int length = to_string(low).size(); length <= to_string(high).size(); ++length) {
for (int start = 1; start <= 10 - length; ++start) {
int num = 0;
for (int i = 0; i < length; ++i) {
num = num * 10 + (start + i);
}
if (num >= low && num <= high)
result.push_back(num);
}
}
sort(result.begin(), result.end());
return result;
}
};
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> result = new ArrayList<>();
int lowLen = String.valueOf(low).length();
int highLen = String.valueOf(high).length();
for (int len = lowLen; len <= highLen; len++) {
for (int start = 1; start <= 10 - len; start++) {
int num = 0;
for (int i = 0; i < len; i++) {
num = num * 10 + (start + i);
}
if (num >= low && num <= high) {
result.add(num);
}
}
}
Collections.sort(result);
return result;
}
}
var sequentialDigits = function(low, high) {
const result = [];
const lowLen = String(low).length;
const highLen = String(high).length;
for (let len = lowLen; len <= highLen; len++) {
for (let start = 1; start <= 10 - len; start++) {
let num = 0;
for (let i = 0; i < len; i++) {
num = num * 10 + (start + i);
}
if (num >= low && num <= high) {
result.push(num);
}
}
}
result.sort((a, b) => a - b);
return result;
};
Given two integers, low and high, find all the numbers within the range [low, high] (inclusive) that have sequential digits.
A number has sequential digits if each digit in the number is exactly one more than the previous digit. For example, 123 and 4567 are sequential digits, but 124 or 135 are not.
Return the list of all such numbers in increasing order. Each digit must be used at most once in a number and only consecutive digits (no skipping) are allowed.
At first glance, the problem might tempt us to check every number between low and high and test whether its digits are sequential. However, this brute-force approach would be inefficient, especially if the range is large.
Instead, we realize that sequential digit numbers have a very specific structure: they always start with a digit from 1 to 9, and each subsequent digit is exactly one greater than the previous. This means there are only a limited number of possible sequential digit numbers, all of which are less than 123456789 (since digits can't repeat or wrap around).
So rather than checking every number in the range, we can generate all possible sequential digit numbers and then filter those that fall within low and high.
Let's break the solution into clear steps:
low and high (let’s call them lowLen and highLen).lowLen and highLen.lowLen to highLen):low and high, include it in the result.This approach is efficient because the total number of sequential digit numbers is small (less than 36 for all possible lengths), so generation and filtering are both fast.
Suppose low = 1000 and high = 13000.
low has 4 digits, high has 5 digits. So we consider lengths 4 and 5.
Each number is generated by starting at a digit and adding the next consecutive digits, and only those within the specified range are kept.
The key insight is that the set of possible sequential digit numbers is very small, so our approach is extremely efficient.
The problem asks for numbers with strictly sequential digits within a range. Instead of checking every number, we generate all possible sequential digit numbers by length and starting digit, then filter those in range. This leverages the structure of the numbers to avoid unnecessary computation, making the solution both elegant and efficient.
The main insight is that the set of sequential digit numbers is small and easy to generate, so we can solve the problem in constant time relative to the input range.