1291. Sequential Digits - Explanation

1. Brute Force

Intuition

A sequential digit number has digits that increase by exactly 1 from left to right (like 123 or 4567). The straightforward approach is to check every number in the range [low, high] and verify if it has sequential digits by comparing adjacent digit characters. While simple to implement, this becomes impractical for large ranges.

Algorithm

Iterate through every number from low to high.
For each number, convert it to a string.
Check if each adjacent pair of digits differs by exactly 1.
If all adjacent pairs satisfy this condition, add the number to the result.
Return the result list.

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []

        for num in range(low, high + 1):
            s = str(num)
            flag = True
            for i in range(1, len(s)):
                if ord(s[i]) - ord(s[i - 1]) != 1:
                    flag = False
                    break
            if flag:
                res.append(num)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Simulation

Intuition

Instead of checking every number, we can generate only the valid sequential digit numbers directly. For a number with d digits starting with digit s, we can build it by appending consecutive digits. For example, starting with 3 and building a 4-digit number gives us 3456. We iterate over all valid digit lengths and starting digits, constructing each candidate and checking if it falls within [low, high].

Algorithm

Determine the digit lengths to consider: from the number of digits in low to that of high.
For each digit length d:
- For each starting digit s from 1 to 9:
  - If s + d > 10, break (not enough consecutive digits available).
  - Build the number by starting with s and appending s+1, s+2, etc.
  - If the result is within [low, high], add it to the result.
Return the result list.

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []
        low_digit, high_digit = len(str(low)), len(str(high))

        for digits in range(low_digit, high_digit + 1):
            for start in range(1, 10):
                if start + digits > 10:
                    break
                num = start
                prev = start
                for i in range(digits - 1):
                    num = num * 10
                    prev += 1
                    num += prev
                if low <= num <= high:
                    res.append(num)
        return res

Time & Space Complexity

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

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

3. Breadth First Search

Intuition

We can think of generating sequential digit numbers as a BFS traversal. Start with single digits 1 through 9 in a queue. For each number, we can extend it by appending the next consecutive digit (if the last digit is less than 9). Processing the queue level by level naturally generates numbers in increasing order of length, and within each length, in increasing order of value.

Algorithm

Initialize a queue with digits 1 through 9.
While the queue is not empty:
- Dequeue a number n.
- If n > high, skip it.
- If n is within [low, high], add it to the result.
- Get the last digit of n. If it's less than 9, enqueue n * 10 + (lastDigit + 1).
Return the result list.

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []
        queue = deque(range(1, 10))

        while queue:
            n = queue.popleft()
            if n > high:
                continue
            if low <= n <= high:
                res.append(n)
            ones = n % 10
            if ones < 9:
                queue.append(n * 10 + (ones + 1))

        return res

Time & Space Complexity

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

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

4. Depth First Search

Intuition

DFS provides another way to enumerate sequential digit numbers. Starting from each single digit (1 to 9), we recursively extend the number by appending the next digit. The recursion naturally explores all valid sequential numbers. Since we start from different initial digits and explore in order, the results may not be sorted, so we sort at the end.

Algorithm

Define a DFS function that takes the current number:
- If the number exceeds high, return.
- If the number is within [low, high], add it to the result.
- If the last digit is less than 9, recurse with num * 10 + (lastDigit + 1).
Call DFS starting from each digit 1 through 9.
Sort the result list and return it.

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []

        def dfs(num):
            if num > high:
                return
            if low <= num <= high:
                res.append(num)
            last_digit = num % 10
            if last_digit < 9:
                dfs(num * 10 + (last_digit + 1))

        for i in range(1, 10):
            dfs(i)

        return sorted(res)

Time & Space Complexity

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

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

5. Sliding Window

Intuition

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.

Algorithm

Define the string nums = "123456789".
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.
Return the result 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

Time & Space Complexity

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

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

Common Pitfalls

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.