An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300 Output: [123,234]
Example 2:
Input: low = 1000, high = 13000 Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
10 <= low <= high <= 10^9Problem Overview: You are given two integers low and high. The task is to return every number within this range whose digits are sequentially increasing, such as 123, 456, or 6789. Each digit must be exactly one greater than the previous digit.
Approach 1: Generate All Sequential Digits and Filter (O(1) time, O(1) space)
The simplest strategy is to pre-generate every possible sequential digit number and then filter the ones that fall inside the range [low, high]. Since digits can only go from 1 to 9, there are fewer than 40 valid sequential numbers in total (e.g., 12, 23, 123, 2345). Store them in a list and iterate through it, adding numbers that satisfy the range condition. The search space is constant because digit length is capped at 9. This approach relies on simple enumeration and works well when you want the most straightforward implementation.
Approach 2: Sliding Window Approach (O(1) time, O(1) space)
Construct sequential numbers using a sliding window over the string "123456789". For each possible window length, slide across the string and convert the substring into an integer. For example, window size 3 generates 123, 234, 345, and so on. Each candidate number is checked against the range [low, high]. This technique avoids hardcoding the numbers and systematically builds them using the sliding window pattern.
Approach 3: Generating Sequential Digits Using Sliding Window (O(1) time, O(1) space)
This variation dynamically builds numbers while iterating over starting digits. Begin with a digit d, then repeatedly append the next digit d+1, d+2, etc., forming numbers like 12, 123, 1234. Stop when the next digit would exceed 9. Each generated number is checked against the bounds. The method is efficient because generation stops early once values exceed high. It is still constant time overall since the number of generated values is bounded.
Approach 4: Iterative Generation with Breadth-First Traversal (O(1) time, O(1) space)
Treat sequential numbers as nodes in a conceptual tree and generate them using a queue. Start with digits 1 through 9. For each number removed from the queue, append the next digit (lastDigit + 1) to create a new sequential number. Push the new number back into the queue if the last digit is less than 9. If the number lies within [low, high], add it to the result. This technique mirrors breadth-first search and naturally generates numbers in increasing order.
Recommended for interviews: The sliding window or BFS generation approach is typically expected. Both show that you recognize the strict digit pattern and avoid brute force checking of every number in the range. Explaining the enumeration first demonstrates understanding, while generating numbers directly shows stronger algorithmic reasoning.
This approach involves generating all possible sequential digit numbers and then filtering them to find the ones within the given range [low, high].
Sequential digit numbers can be viewed as forming an arithmetic sequence where the difference between consecutive digits is one. Starting with single-digit numbers, we generate all possible sequential numbers by adding the next digit until the number exceeds the upper limit. By maintaining a list of such numbers, we can iterate over this list and select numbers that fall within the specified range.
This Python function initializes a list result to store potential sequential digit numbers. By iterating the start value from 1 through 9, we form an initial number num and apply a while loop to generate sequential numbers by appending the next digit. For each valid num, we check if it lies within the range [low, high] and add it to the result.
Python
Time Complexity: O(1) - Determined by the fixed number of sequential digits.
Space Complexity: O(1) - Space used is constant due to the limited number of sequential digit numbers.
Another approach utilizes a sliding window to generate possible sequences. By sliding over a pre-defined string of digits from '1' to '9', we construct numbers by considering substrings of increasing length. If digits form a number larger than high, we stop further expansion of that sequence.
This solution uses a predefined string '123456789' to simulate a sliding window effect. By varying the window length from 2 to 9, it generates numbers by converting substrings to integers. Valid numbers are collected in the list result.
Python
Time Complexity: O(1) - Since there are maximum 45 possible numbers derived from the digit string of length 9.
Space Complexity: O(1) - Limited and fixed space occupation.
This approach involves generating all possible sequential digits by using a string representation of numbers and sliding over them with different lengths. By maintaining a starting digit, we can build numbers by appending increasing numbers to it.
The above function iterates over possible lengths of sequential numbers fitting in the range dictated by the number of digits in low and high. It slides over the sequential string "123456789" and creates numbers of a specific length. If a generated number is within the range, it's appended to a result list.
Time Complexity: O(1) relative to the constant set of sequential digits.
Space Complexity: O(1) for results storage, limited by specific constraints.
This approach uses an iterative method to generate numbers by extending in a breadth-first manner. Starting from each single-digit as a potential number, extend by appending one higher digit until the maximum range limit is reached.
This Java solution utilizes a queue to explore the current number by appending a higher digit, similar to how BFS explores levels of a graph. The digits are expanded sequentially until the high constraint is breached.
Java
JavaScript
Time Complexity: O(1) for the bounded number of operations as digits are limited.
Space Complexity: O(1) with respect to storing valid outputs within range constraints.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Generate All Sequential Digits and Filter | Time Complexity: O(1) - Determined by the fixed number of sequential digits. |
| Approach 2: Sliding Window Approach | Time Complexity: O(1) - Since there are maximum 45 possible numbers derived from the digit string of length 9. |
| Generating Sequential Digits Using Sliding Window | Time Complexity: O(1) relative to the constant set of sequential digits. |
| Iterative Generation with Breadth-First Traversal | Time Complexity: O(1) for the bounded number of operations as digits are limited. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Sequential Digits and Filter | O(1) | O(1) | Simplest implementation when you precompute all possible sequential numbers. |
| Sliding Window on "123456789" | O(1) | O(1) | Clean pattern-based generation without storing predefined values. |
| Dynamic Sequential Generation | O(1) | O(1) | When building numbers incrementally from each starting digit. |
| Breadth-First Traversal (Queue) | O(1) | O(1) | Useful when demonstrating BFS-style generation and producing numbers in sorted order. |
Sequential Digits - Leetcode 1291 - Python • NeetCodeIO • 14,903 views views
Watch 9 more video solutions →Practice Sequential Digits with our built-in code editor and test cases.
Practice on FleetCode