Formatted question description: https://leetcode.ca/all/1215.html

# 1215. Stepping Numbers

## Level

Medium

## Description

A *Stepping Number* is an integer such that all of its adjacent digits have an absolute difference of exactly `1`

. For example, `321`

is a Stepping Number while `421`

is not.

Given two integers `low`

and `high`

, find and return a **sorted list** of all the Stepping Numbers in the range `[low, high]`

inclusive.

**Example 1:**

**Input:** low = 0, high = 21

**Output:** [0,1,2,3,4,5,6,7,8,9,10,12,21]

**Constraints:**

`0 <= low <= high <= 2 * 10^9`

## Solution

First find all the Stepping Numbers from 0 to 10^d where d is the length of `high`

. Obviously, all 1-digit numbers from 0 to 9 are Stepping Numbers. Starting from 1-digit numbers 1 to 9 (0 is not included here since any other number cannot have leading zeros), obtain the Stepping Numbers that have one greater length. For example, for the number 20, the next Stepping Number is 201. For the number 25, the next Stepping Numbers are 254 and 256. For the number 29, the next Stepping Number is 298. Since the numbers may be very large, use data type `Long`

to represent the numbers. It is guaranteed that all the Stepping Numbers that are obtained are sorted.

After all the Stepping Numbers are obtained, use binary search to find the start index `startIndex`

and the end index `endIndex`

in the list of Stepping Numbers, where the number at ``startIndex` is the minimum Stepping Number that is greater than or equal to `

low`, and the number at `

endIndex` is the maximum Stepping Number that is less than or equal to `

high`. Use a list of type `

Integer` to store all the Stepping Numbers in the indices range `

[startIndex, endIndex]` of all the Stepping Numbers, and return the final list.

```
class Solution {
public List<Integer> countSteppingNumbers(int low, int high) {
int maxLength = String.valueOf(high).length();
List<Long> allSteppingNumbers = new ArrayList<Long>();
Queue<Long> queue = new LinkedList<Long>();
allSteppingNumbers.add(0L);
for (long i = 1; i <= 9; i++) {
allSteppingNumbers.add(i);
queue.offer(i);
}
int length = 1;
while (length < maxLength) {
length++;
int size = queue.size();
for (int i = 0; i < size; i++) {
long num = queue.poll();
long lastDigit = num % 10;
if (lastDigit > 0) {
long newNum = num * 10 + lastDigit - 1;
allSteppingNumbers.add(newNum);
queue.offer(newNum);
}
if (lastDigit < 9) {
long newNum = num * 10 + lastDigit + 1;
allSteppingNumbers.add(newNum);
queue.offer(newNum);
}
}
}
int startIndex = binarySearch(allSteppingNumbers, low);
int endIndex = binarySearch(allSteppingNumbers, high);
if (startIndex < 0)
startIndex = -startIndex - 1;
if (endIndex < 0)
endIndex = -endIndex - 2;
List<Integer> steppingNumbers = new ArrayList<Integer>();
for (int i = startIndex; i <= endIndex; i++) {
long numLong = allSteppingNumbers.get(i);
steppingNumbers.add((int) numLong);
}
return steppingNumbers;
}
public int binarySearch(List<Long> list, int key) {
int low = 0, high = list.size() - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
long num = list.get(mid);
if (num == key)
return mid;
else if (num > key)
high = mid - 1;
else
low = mid + 1;
}
return -low - 1;
}
}
```