1291. Sequential Digits

Description

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

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(36 -> 1)
• Space complexity: O(9 -> 1)

 

JavaScript

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
const sequentialDigits = function (low, high) {
  const result = [];
  let queue = [1, 2, 3, 4, 5, 6, 7, 8, 9];

  while (queue.length) {
    const nextQueue = [];

    for (const num of queue) {
      if (num > high) continue;

      if (num >= low) {
        result.push(num);
      }

      const prev = num % 10;
      const nextDigit = prev + 1;

      if (nextDigit > 9) continue;

      nextQueue.push(num * 10 + nextDigit);
    }

    queue = nextQueue;
  }

  return result;
};