# Sequential Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sequential-digits)
Canonical: https://scaleengineer.com/dsa/problems/sequential-digits
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## Problem
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^9`

# Approaches
## Brute-Force Iteration
This approach involves iterating through every integer from `low` to `high`. For each integer, we perform a check to see if its digits are sequential. If they are, the integer is added to our result list.
**Time:** O(N * L), where N is the number of integers in the range `[low, high]` (i.e., `high - low + 1`) and L is the number of digits in the integer. Since `high` can be up to `10^9`, L is at most 10. The complexity can be written as O((high - low) * log10(high)). This is very slow for large ranges. · **Space:** O(log10(high)). The space is dominated by the storage required for the string representation of the number being checked. The result list stores at most 36 numbers, which is constant space.
**Pros:** Simple to understand and implement.; Requires minimal logic beyond the problem definition.
**Cons:** Highly inefficient for large ranges between `low` and `high`.; Will likely result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms due to its high time complexity.
### Explanation
The most straightforward way to solve this problem is to check every single number in the given range. We can create a helper function, say `isSequential(n)`, that takes an integer and returns `true` if its digits are sequential and `false` otherwise.

Inside `isSequential(n)`, we can convert the number `n` to a string to easily access its digits. Then, we iterate through the digits from the first to the second-to-last. In each step, we check if the next digit is exactly one more than the current digit. If this condition ever fails, we immediately know the number is not sequential and can return `false`. If the loop completes without finding any non-sequential pairs, the number is sequential, and we return `true`.

The main function will loop from `low` to `high`. For each number `i` in the loop, it calls `isSequential(i)`. If `isSequential(i)` returns `true`, `i` is added to the result list. Since we iterate in increasing order, the list will be naturally sorted.

```java
class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> result = new ArrayList<>();
        for (int i = low; i <= high; i++) {
            if (isSequential(i)) {
                result.add(i);
            }
        }
        return result;
    }

    private boolean isSequential(int n) {
        String s = String.valueOf(n);
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i + 1) - s.charAt(i) != 1) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Loop for `num` from `low` to `high`.
- For each `num`, check if it has sequential digits using a helper function `isSequential(num)`.
- The `isSequential` function works as follows:
  - Convert the number `num` to its string representation, `s`.
  - Iterate from the first character to the second-to-last character of `s`.
  - In each step, check if the character at the next position is exactly one greater than the character at the current position (e.g., `s.charAt(i+1) - s.charAt(i) == 1`).
  - If this condition ever fails, the number is not sequential, so return `false`.
  - If the loop completes without returning, it means all digits are sequential, so return `true`.
- If `isSequential(num)` returns `true`, add `num` to the `result` list.
- After checking all numbers up to `high`, return the `result` list. The list will be sorted because we iterate from `low` to `high`.

## Generation using Breadth-First Search (BFS)
A much more efficient approach is to realize that the total number of integers with sequential digits is very small and fixed. We can generate all of them first, and then simply filter out the ones that fall within the given `[low, high]` range.
**Time:** O(1). The number of sequential digits is constant and small (36 in total). The generation process performs a constant number of operations, regardless of the `low` and `high` values. · **Space:** O(1). The space used by the queue is constant, as it will hold at most 8 numbers at any given time (e.g., 12, 23, ..., 89). The result list also stores at most 36 numbers.
**Pros:** Extremely efficient and fast, with a constant time complexity.; The performance is independent of the size of the range `[low, high]`.
**Cons:** Requires more insight into the problem's structure compared to the brute-force approach.; The implementation, while not complex, involves more data structures (a queue).
### Explanation
The key observation is that there are only a limited number of sequential digit numbers (e.g., 12, 234, 5678, etc.). The smallest is 12 and the largest is 123456789. Instead of checking every number in a potentially vast range, we can just generate this small set of valid numbers and see which ones fit our criteria.

A clean way to generate these numbers in sorted order is to use a Breadth-First Search (BFS) approach. We can think of the numbers as nodes in a tree where a number `N` has a child `N*10 + (last_digit_of_N + 1)`.

We start by seeding a queue with the single-digit numbers (1 to 9). Then, we iteratively take a number from the queue, check if it's in our `[low, high]` range, and then generate the next sequential number to add back to the queue. We stop generating children for a number if its last digit is 9 or if the number itself exceeds `high`.

This method naturally generates the numbers in ascending order (1, 2, ..., 9, 12, 23, ..., 89, 123, ...), so the final result list will be sorted as required.

```java
class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        // Initialize the queue with single-digit numbers (our starting points)
        for (int i = 1; i <= 9; i++) {
            queue.add(i);
        }

        while (!queue.isEmpty()) {
            int current = queue.poll();

            // If the current number is within the desired range, add it.
            if (current >= low && current <= high) {
                result.add(current);
            }

            // If current exceeds high, no need to check further from this path.
            if (current > high) {
                continue; // or break, since queue is ordered
            }

            int lastDigit = current % 10;
            // If the last digit is not 9, we can form a longer sequential number.
            if (lastDigit < 9) {
                int nextNum = current * 10 + (lastDigit + 1);
                if (nextNum <= high) {
                    queue.add(nextNum);
                }
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Initialize a queue (e.g., `LinkedList`) and add the single-digit numbers 1 through 9 to it. These are the seeds for all sequential numbers.
- Start a loop that continues as long as the queue is not empty.
  - Dequeue an element, let's call it `current`.
  - If `current` is within the range `[low, high]`, add it to the `result` list.
  - If `current` is greater than `high`, we can stop processing because all subsequent numbers generated will also be larger. Break the loop.
  - Get the last digit of `current`: `lastDigit = current % 10`.
  - If `lastDigit < 9`, it's possible to form a longer sequential number.
    - Calculate the next sequential number: `nextNum = current * 10 + (lastDigit + 1)`.
    - If `nextNum` is not greater than `high`, add it to the queue.
- Return the `result` list. It is already sorted because the BFS-like generation produces numbers in increasing order.

# Solutions
### Java

```java
class Solution { public List < Integer > sequentialDigits ( int low , int high ) { List < Integer > ans = new ArrayList <>(); for ( int i = 1 ; i < 9 ; ++ i ) { int x = i ; for ( int j = i + 1 ; j < 10 ; ++ j ) { x = x * 10 + j ; if ( x >= low && x <= high ) { ans . add ( x ); } } } Collections . sort ( ans ); return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > sequentialDigits ( int low , int high ) { vector < int > ans ; for ( int i = 1 ; i < 9 ; ++ i ) { int x = i ; for ( int j = i + 1 ; j < 10 ; ++ j ) { x = x * 10 + j ; if ( x >= low && x <= high ) { ans . push_back ( x ); } } } sort ( ans . begin (), ans . end ()); return ans ; } };
```

### Python

```python
class Solution : def sequentialDigits ( self , low : int , high : int ) -> List [ int ]: ans = [] for i in range ( 1 , 9 ): x = i for j in range ( i + 1 , 10 ): x = x * 10 + j if low <= x <= high : ans . append ( x ) return sorted ( ans )
```