Leetcode 1215. Stepping Numbers

Problem Explanation:

A stepping number is a number in which the absolute difference between all neighboring digits is exactly one. For example, let's consider the number 321, the absolute difference between 3 and 2 is 1 and 2 and 1 is also 1, which makes it a stepping number. Similarly, let's take 421, the absolute difference between 4 and 2 is not 1, hence 421 is not a stepping number.

In this problem, the objective is to find all the stepping numbers in a given range. We are provided two integers low and high, we need to implement a function that returns a sorted list of all stepping numbers in the range [low, high] inclusive.

For example, for the range [0, 21], the stepping numbers are [0,1,2,3,4,5,6,7,8,9,10,12,21].

Approach of Solution:

The solution demonstrates the use of the breadth-first search (BFS) algorithm where all numbers starting from 1 to 9 are pushed into a queue. Next, pop a number from the front of the queue, and check if this number lies in the range low to high then, and if yes then we add this number to our answer list. Perform a check on the last digit of the popped number to decide the next candidate number. If the last digit of the number is 0 then the next candidate number will be num*10 + lastDigit + 1, otherwise, we will have two candidate numbers num * 10 + lastDigit - 1 and num * 10 + lastDigit + 1.

Python Solution

1
2python
3from queue import Queue
4class Solution:
5    def countSteppingNumbers(self, low: int, high: int) -> List[int]:
6        result = []
7        if low == 0:
8            result.append(0)
9        queue = Queue()
10        for digit in range(1, 10):
11            queue.put(digit)
12
13        while not queue.empty():
14            stepNum = queue.get()
15            if low <= stepNum <= high:
16                result.append(stepNum)
17
18            if stepNum == 0 or stepNum > high:
19                continue
20
21            lastDigit = stepNum % 10
22
23            # There can be 2 cases either digit to be appended
24            # is lastDigit + 1 or lastDigit - 1
25            stepNumA = stepNum * 10 + (lastDigit - 1)
26            stepNumB = stepNum * 10 + (lastDigit + 1)
27
28            # If last digit is 0 then only possible digit after 0
29            # can be 1 for a Stepping Number
30            if lastDigit == 0:
31                queue.put(stepNumB)
32
33            # If last digit is 9 then only possible
34            # digit after 9 can be 8 for a Stepping number
35            elif lastDigit == 9:
36                queue.put(stepNumA)
37
38            else:
39                queue.put(stepNumA)
40                queue.put(stepNumB)
41
42        return result

This Python solution creates a list of stepping numbers by generating them one by one from 1 to 9 using BFS and pushing them into a queue. After each generation, it verifies if the generated stepping number lies within the required range before adding it to the result list. If the stepping number is greater than the high limit or equal to zero, it skips the loop's remaining iterations. At last, Python's built-in sorted function is used to return the sorted list of stepping numbers.

JavaScript Solution

Javascript solution for the problem will be similar to the Python solution. We will use an array as a queue instead of using a built-in queue.

1
2javascript
3var countSteppingNumbers = function(low, high) {
4    let result = [];
5    if (low === 0) {
6        result.push(0);
7    }
8    let queue = [];
9    for (let digit = 1; digit < 10; digit++) {
10        queue.push(digit);
11    }
12
13    while (queue.length !== 0) {
14        let stepNum = queue.shift();
15        if (low <= stepNum && stepNum <= high) {
16            result.push(stepNum);
17        }
18
19        if (stepNum === 0 || stepNum > high) {
20            continue;
21        }
22
23        let lastDigit = stepNum % 10;
24        let stepNumA = stepNum * 10 + (lastDigit - 1);
25        let stepNumB = stepNum * 10 + (lastDigit + 1);
26
27        if (lastDigit === 0) {
28            queue.push(stepNumB);
29        } else if (lastDigit === 9) {
30            queue.push(stepNumA);
31        } else {
32            queue.push(stepNumA);
33            queue.push(stepNumB);
34        }
35    }
36    return result.sort((a, b) => a - b);
37};

Java Solution

The Java solution uses a LinkedList as a queue. LinkedList in Java can be used as a Queue as it implements the Deque interface.

1
2java
3import java.util.LinkedList;
4import java.util.List;
5
6class Solution {
7    
8    public List<Integer> countSteppingNumbers(int low, int high) {
9        
10        List<Integer> result = new LinkedList<>();
11        if(low == 0){
12            result.add(0);
13        }
14        
15        LinkedList<Long> queue = new LinkedList<>();
16        for(long digit = 1; digit < 10; digit++){
17            queue.add(digit);
18        }
19        while(!queue.isEmpty()){
20            Long stepNum = queue.removeFirst();
21            if(low <= stepNum && stepNum <= high){
22                result.add(stepNum.intValue());
23            }
24            if(stepNum == 0 || stepNum > high){
25                continue;
26            }
27            long lastDigit = stepNum % 10;
28            long stepNmA = stepNum * 10 + (lastDigit - 1);
29            long stepNmB = stepNum * 10 + (lastDigit + 1);
30            if(lastDigit == 0){
31                queue.add(stepNmB);
32            }else if(lastDigit == 9){
33                queue.add(stepNmA);
34            }else{
35                queue.add(stepNmA);
36                queue.add(stepNmB);
37            }
38        }
39        return result;
40
41    }
42}

The number that gets added to the queue is of type long because the number can exceed the limit of integer in java. Afterwards convert long to integer before adding to result and return result as List of integers.