Watch 10 video solutions for Sequential Digits, a medium level problem involving Enumeration. This walkthrough by NeetCodeIO has 14,903 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |