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.

Examples

Example 1

1
2

Input: low = 100, high = 300
Output: [123,234]

Example 2

1
2

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints

  • 10 <= low <= high <= 10^9

Solution

Method 1 – Enumeration by Length

Intuition

Sequential digits numbers are rare and can be generated by starting from each digit 1-9 and appending the next digit until 9. We can enumerate all such numbers and filter those in the given range.

Approach

  1. For each possible length from the number of digits in low to high:
    • For each starting digit from 1 to 9:
      • Build the sequential number by appending increasing digits.
      • If the number is in [low, high], add to the answer.
  2. Return the sorted list of valid numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> sequentialDigits(int low, int high) {
        vector<int> ans;
        for (int len = to_string(low).size(); len <= to_string(high).size(); ++len) {
            for (int start = 1; start <= 10 - len; ++start) {
                int num = 0;
                for (int d = 0; d < len; ++d) num = num * 10 + (start + d);
                if (num >= low && num <= high) ans.push_back(num);
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func sequentialDigits(low int, high int) []int {
    res := []int{}
    for l := len(fmt.Sprint(low)); l <= len(fmt.Sprint(high)); l++ {
        for start := 1; start <= 10-l; start++ {
            n := 0
            for d := 0; d < l; d++ {
                n = n*10 + start + d
            }
            if n >= low && n <= high {
                res = append(res, n)
            }
        }
    }
    sort.Ints(res)
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> ans = new ArrayList<>();
        int minLen = String.valueOf(low).length(), maxLen = String.valueOf(high).length();
        for (int len = minLen; len <= maxLen; ++len) {
            for (int start = 1; start <= 10 - len; ++start) {
                int num = 0;
                for (int d = 0; d < len; ++d) num = num * 10 + (start + d);
                if (num >= low && num <= high) ans.add(num);
            }
        }
        Collections.sort(ans);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun sequentialDigits(low: Int, high: Int): List<Int> {
        val ans = mutableListOf<Int>()
        val minLen = low.toString().length
        val maxLen = high.toString().length
        for (len in minLen..maxLen) {
            for (start in 1..(10-len)) {
                var num = 0
                for (d in 0 until len) num = num * 10 + (start + d)
                if (num in low..high) ans.add(num)
            }
        }
        ans.sort()
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def sequentialDigits(self, low: int, high: int) -> list[int]:
        ans = []
        for l in range(len(str(low)), len(str(high)) + 1):
            for start in range(1, 11 - l):
                num = 0
                for d in range(l):
                    num = num * 10 + start + d
                if low <= num <= high:
                    ans.append(num)
        ans.sort()
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn sequential_digits(low: i32, high: i32) -> Vec<i32> {
        let mut ans = vec![];
        let min_len = low.to_string().len();
        let max_len = high.to_string().len();
        for len in min_len..=max_len {
            for start in 1..=(10-len) {
                let mut num = 0;
                for d in 0..len {
                    num = num * 10 + (start + d) as i32;
                }
                if num >= low && num <= high {
                    ans.push(num);
                }
            }
        }
        ans.sort();
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    sequentialDigits(low: number, high: number): number[] {
        const ans: number[] = [];
        const minLen = low.toString().length, maxLen = high.toString().length;
        for (let len = minLen; len <= maxLen; ++len) {
            for (let start = 1; start <= 10 - len; ++start) {
                let num = 0;
                for (let d = 0; d < len; ++d) num = num * 10 + start + d;
                if (num >= low && num <= high) ans.push(num);
            }
        }
        ans.sort((a, b) => a - b);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(1), since the number of sequential digits numbers is at most 36 (for 2 to 9 digits).
  • 🧺 Space complexity: O(1), for the output list (ignoring output size).