Sequential Digits

How it works

All sequential digit numbers are substrings of "123456789". A 2-digit sequential number is a substring of length 2, a 3-digit one is length 3, and so on. By sliding a window of each valid length across this master string and converting substrings to integers, we generate all possible sequential digit numbers directly.

Steps

1. Define the string nums = "123456789".
2. For each window size d from 2 to 9:
   • Slide the window across nums:
     • Extract the substring of length d starting at index i.
     • Convert it to an integer.
     • If it exceeds high, break the inner loop.
     • If it is within [low, high], add it to the result.
3. Return the result list.

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Since, we have at most 36 valid numbers as per the given constraints.

Things to watch for

Not Recognizing the Limited Search Space

A common mistake is using a brute force approach that iterates through every number in the range [low, high]. Since there are only 36 possible sequential digit numbers (from "12" to "123456789"), iterating through potentially billions of numbers is extremely inefficient. Recognize that you should generate only the valid candidates.

Forgetting the Upper Bound on Starting Digits

When building sequential digit numbers of length d, the starting digit cannot exceed 10 - d. For example, a 4-digit sequential number cannot start with 7, 8, or 9 because there are not enough consecutive digits remaining. Failing to enforce this constraint leads to invalid numbers like "7890" which wraps around.

Returning Results Out of Order

Some approaches like DFS generate numbers in an order that is not sorted (e.g., 12, 123, 1234, ..., 23, 234, ...). The problem expects results in ascending order. Remember to sort the final result if your generation method does not naturally produce sorted output.

from typing import List

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        nums = "123456789"
        res = []
        for d in range(2, 10):
            for i in range(9 - d + 1):
                num = int(nums[i: i + d])
                if num > high:
                    break
                if low <= num <= high:
                    res.append(num)
        return res

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        string nums = "123456789";
        vector<int> res;

        for (int d = 2; d <= 9; d++) {
            for (int i = 0; i <= 9 - d; i++) {
                int num = stoi(nums.substr(i, d));
                if (num > high) {
                    break;
                }
                if (num >= low && num <= high) {
                    res.push_back(num);
                }
            }
        }

        return res;
    }
};