1291. Sequential Digits

Problem Statement in English

You’re given two integers low and high. You have to find all the integers in the range [low, high] that have sequential digits.

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] that have sequential digits.

Approach

There’s a little observation here that makes this problem much more manageable.

Any sequential digit will have to be a substring of 123456789.

So we can use a sliding window of size window to generate all the sequential digits of that size, that also match the criteria of being between low and high.

We can also make the tiny optimization of only generating sequential digits of size between the number of digits in low and the number of digits in high, since any sequential digit outside that range would not be valid. So we can break out of the loop early whenever we generate a sequential digit that is greater than high, and move on to the next window size.

And we’re done!

Solution in Python

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

        s = "123456789"
        start = len(str(low))
        end = len(str(high))

        for window in range(start, end + 1):
            for r in range(window - 1, len(s)):
                temp = int(s[r - window + 1:r + 1])
                if low <= temp <= high:
                    res.append(temp)
                elif temp > high:
                    break

        return sorted(res)

Complexity

• Time: $O(1)$
  Since the number of sequential digits is limited and does not depend on the input size.

• Space: $O(1)$
  Since we’re not using any extra space.

And we are done.