Problem 1291

Question statement

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.

Solution

Main idea:

The key realization comes from the fact that between $10^{k}$ and $10^{k+1}$, the first sequential number is $12\dots k$, and every subsequent sequential number can be obtained by adding $11\dots1$ to the previous sequential number (and stopping when the unit digit becomes $9$). We store all these number into an array ans. Then we move on to the range $10^{k+1}$ to $10^{k+2}$. Clamp this process to the range [low, high] and return the ans.

Code:

def sequentialDigits(self, low: int, high: int) -> List[int]:
    cts_str = '1234567899'
    min_exp = len(str(low))-1
    max_exp = len(str(high))-1
    ans = []
    for i in range(min_exp, max_exp+1):
        to_add = int('1'*(i+1))
        cur = int(cts_str[:i+1])
        while(cur < 10**(i+1) and cur <= high and cur % 10 != 0):
            if(cur < low):
                cur+=to_add
                continue
            ans.append(cur)
            cur+=to_add
    return ans

Comments:

Time complexity: O(n) where $n= \texttt{(high - low)/min_exp}$

At the time of submission, the above solution passes leetcode submission cases in 26ms, beats 95.11% of users. It uses 16.64MB of memory, beating 52.60% of users.