Skip to content

1291. Sequential Digits 👍

  • Time: $O(9\log\texttt{high}) = O(\log\texttt{high})$
  • Space: $O(\log\texttt{high})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<int> sequentialDigits(int low, int high) {
    vector<int> ans;
    queue<int> q{{1, 2, 3, 4, 5, 6, 7, 8, 9}};

    while (!q.empty()) {
      const int num = q.front();
      q.pop();
      if (num > high)
        return ans;
      if (low <= num && num <= high)
        ans.push_back(num);
      const int lastDigit = num % 10;
      if (lastDigit < 9)
        q.push(num * 10 + lastDigit + 1);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public List<Integer> sequentialDigits(int low, int high) {
    List<Integer> ans = new ArrayList<>();
    Queue<Integer> q = new ArrayDeque<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9));

    while (!q.isEmpty()) {
      final int num = q.poll();
      if (num > high)
        return ans;
      if (low <= num && num <= high)
        ans.add(num);
      final int lastDigit = num % 10;
      if (lastDigit < 9)
        q.offer(num * 10 + lastDigit + 1);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def sequentialDigits(self, low: int, high: int) -> list[int]:
    ans = []
    q = collections.deque([num for num in range(1, 10)])

    while q:
      num = q.popleft()
      if num > high:
        return ans
      if low <= num and num <= high:
        ans.append(num)
      lastDigit = num % 10
      if lastDigit < 9:
        q.append(num * 10 + lastDigit + 1)

    return ans