1215. Stepping Numbers

MediumBreadth-First SearchBacktracking
Leetcode Link

Problem Description

We need to find all "stepping numbers" between two integers low and high, inclusive. A stepping number is defined as a number in which each digit is one more or one less than its neighboring digits. For example, 123 and 987 are stepping numbers, but 135 and 975 are not. The task is to produce a list of these particular numbers in sorted order without skipping any in the given range.

Intuition

The concept is similar to a breadth-first search (BFS) on the numbers, but with a unique condition that defines our graph's edges: a number can only connect to another if they differ by one at the last digit. Since single-digit numbers naturally fit the stepping number definition (except for 0 which has only one neighbor), we use them as the starting points for our BFS queue, except for 0 which we include directly into the results if it's within the given range.

From each single-digit number 1 to 9, we construct new numbers by appending a digit either one less or one more than the last digit (if possible), ensuring this new number is still a stepping number. We continue this process in a BFS manner, checking at each step if our current number falls within the desired range low to high. If it does, we include it in the results. The stopping condition for our BFS is when a number exceeds high, ensuring we are not wasting resources by continuing the search beyond the given range.

By using BFS, we also take advantage of the fact that the queue keeps numbers approximately in the order of their magnitude, helping to fulfill the requirement that the list we return is sorted.

Learn more about Breadth-First Search and Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The solution approach involves implementing a Breadth-First Search (BFS) algorithm. BFS is typically used to traverse or search tree or graph data structures. It starts at some arbitrary node of a graph (or root of a tree) and explores the neighbor nodes first, before moving to the next level neighbors. Here's how the BFS is used to find stepping numbers:

  • First, we check if 0 is within the inclusive range given by low and high. If it is, we add 0 to the answer list because 0 is considered a stepping number.

  • Then, we initialize a queue q and add the digits 1 to 9 to it. These are our starting points for generating stepping numbers since each single digit is trivially a stepping number.

  • Now we follow the BFS pattern: We continuously process items from the queue until the queue is empty or we've exceeded our high limit. For each element v that we pop from the queue, we do the following:

    • Check if v is greater than high. If it is, we break from the loop as further numbers will only be larger and outside our range.

    • If v is within the range [low, high], we add v to our list of answers, ans.

    • Next, we need to generate the potential stepping numbers that can be formed using v as the base. To do this, we consider the last digit x of v.

    • If x > 0, i.e., it's possible to subtract one from it without getting a negative digit, we generate a new number by appending x - 1 to v, and we add v * 10 + x - 1 to the queue.

    • If x < 9, i.e., we can add one to the digit without exceeding 9, we create another number by appending x + 1 to v, and we add v * 10 + x + 1 to the queue.

  • This process continues, growing numbers at the queue's front by one digit at a time, always checking that they are stepping numbers.

  • Finally, when the queue is empty, or all remaining numbers in the queue are greater than high, the BFS search is complete. The ans list, which has been constructed in ascending order due to the nature of BFS, contains all the stepping numbers in the range [low, high].

This algorithm employs BFS effectively to navigate the space of numbers, efficiently filtering and constructing stepping numbers. It uses the queue q to keep track of candidates for stepping numbers and a list ans to store the final results in sorted order.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's take a small range to illustrate the solution approach. Assume our low is 10 and high is 21. Here is how the algorithm would execute to find stepping numbers in this range:

  1. Initialize the result list ans and check if 0 is within the range 10 to 21. It is not, so we do not add 0 to ans.

  2. Initialize the queue q and add the digits 1 to 9 to it, because these are already stepping numbers.

  3. Start the BFS by dequeuing the front of q and processing it. The process starts with 1.

  4. Since 1 is less than low, it is not added to the ans, but we will use it to generate potential stepping numbers. We check for the last digit x of 1, which is 1. We can subtract 1 to get 0 and add 1 to get 2. We generate 10 and 12 and add them to the queue.

  5. Continue the BFS. The next number in the queue would be 2, and we will follow the same steps to generate 21 and 23 and add to the queue. Since 21 is within the range [10, 21], it is added to ans.

  6. The same process continues for queue elements 3 through 9 but all the numbers each would generate (30 and 32 for 3, 43 and 45 for 4, and so on) would be greater than the high of 21, so they do not contribute to the ans list.

  7. At this stage our BFS is mostly generating numbers that are higher than 21. Once the number at the front of the queue is 22 or higher, the BFS stops processing new numbers.

  8. The final ans list contains the stepping numbers in the given range: [10, 12, 21].

The algorithm uses the BFS to systematically explore larger and larger stepping numbers starting from the smallest possible ones (the single-digit numbers) while checking against the low and high constraints to build a sorted result list.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def count_stepping_numbers(self, low: int, high: int) -> List[int]:
6        # Initialize an empty list to store stepping numbers
7        stepping_numbers = []
8      
9        # Add 0 to the list if the range starts from 0 because 0 is a stepping number
10        if low == 0:
11            stepping_numbers.append(0)
12      
13        # Create a queue and initialize it with numbers 1 through 9
14        # These serve as starting points for generating stepping numbers
15        queue = deque(range(1, 10))
16      
17        # Process the queue until it's empty
18        while queue:
19            # Pop the first element in the queue
20            current = queue.popleft()
21          
22            # If the current number exceeds the high limit, exit the loop
23            if current > high:
24                break
25          
26            # If the current number is within the specified range, add it to the result list
27            if current >= low:
28                stepping_numbers.append(current)
29          
30            # Get the last digit of the current number to calculate next possible stepping numbers
31            last_digit = current % 10
32          
33            # Generate the next number by appending a digit smaller by 1 (if possible) and larger by 1 (if possible)
34            if last_digit:
35                queue.append(current * 10 + last_digit - 1)
36            if last_digit < 9:
37                queue.append(current * 10 + last_digit + 1)
38      
39        # Return the list of stepping numbers
40        return stepping_numbers
41
42# Example of how the code can be used:
43# solution = Solution()
44# print(solution.count_stepping_numbers(0, 21))
45
1class Solution {
2  
3    // Function to return all stepping numbers between the range [low, high]
4    public List<Integer> countSteppingNumbers(int low, int high) {
5        List<Integer> steppingNumbers = new ArrayList<>();
6      
7        // Add 0 as a stepping number if it's within the range
8        if (low == 0) {
9            steppingNumbers.add(0);
10        }
11      
12        // Create a queue to perform Breadth First Search (BFS)
13        Deque<Long> queue = new ArrayDeque<>();
14      
15        // Seed the queue with numbers 1 to 9 as they are the single-digit stepping numbers
16        for (long i = 1; i < 10; i++) {
17            queue.offer(i);
18        }
19
20        // Perform BFS to find all stepping numbers
21        while (!queue.isEmpty()) {
22            long currentNumber = queue.pollFirst();
23          
24            // Terminate BFS when the current number exceeds the upper bound
25            if (currentNumber > high) {
26                break;
27            }
28          
29            // Add the current number to the result list if it's within the range
30            if (currentNumber >= low) {
31                steppingNumbers.add((int) currentNumber);
32            }
33          
34            // Get the last digit of the current number
35            int lastDigit = (int) currentNumber % 10;
36          
37            // Generate next stepping number by appending a valid digit
38          
39            // If the last digit is not 0, append (lastDigit - 1)
40            if (lastDigit > 0) {
41                queue.offer(currentNumber * 10 + lastDigit - 1);
42            }
43          
44            // If the last digit is not 9, append (lastDigit + 1)
45            if (lastDigit < 9) {
46                queue.offer(currentNumber * 10 + lastDigit + 1);
47            }
48        }
49      
50        // Return the complete list of stepping numbers
51        return steppingNumbers;
52    }
53}
54
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    // Function to find all stepping numbers between low and high
7    vector<int> countSteppingNumbers(int low, int high) {
8        // Container to hold the final list of stepping numbers
9        vector<int> steppingNumbers;
10      
11        // If zero is within the range, add it to the list
12        if (low == 0) {
13            steppingNumbers.push_back(0);
14        }
15      
16        // Queue to facilitate the breadth-first search
17        queue<long long> bfsQueue;
18      
19        // Initialize the queue with numbers 1 through 9
20        for (int digit = 1; digit < 10; ++digit) {
21            bfsQueue.push(digit);
22        }
23      
24        // Perform BFS to generate stepping numbers
25        while (!bfsQueue.empty()) {
26            // Extract the front element from the queue
27            long long currentNumber = bfsQueue.front();
28            bfsQueue.pop();
29          
30            // If the current number is greater than the high limit, stop the search
31            if (currentNumber > high) {
32                break;
33            }
34          
35            // If the current number lies within the range, add it to the result list
36            if (currentNumber >= low) {
37                steppingNumbers.push_back(currentNumber);
38            }
39          
40            // Calculate the last digit of the current number
41            int lastDigit = currentNumber % 10;
42          
43            // Generate the next stepping number and add it to the queue if the last digit is not 0
44            if (lastDigit > 0) {
45                long long nextSteppingNumber = currentNumber * 10 + lastDigit - 1;
46                bfsQueue.push(nextSteppingNumber);
47            }
48          
49            // Generate the next stepping number and add it to the queue if the last digit is not 9
50            if (lastDigit < 9) {
51                long long nextSteppingNumber = currentNumber * 10 + lastDigit + 1;
52                bfsQueue.push(nextSteppingNumber);
53            }
54        }
55      
56        // Return the final list of stepping numbers
57        return steppingNumbers;
58    }
59};
60
1// Function to find all stepping numbers in a given range.
2function countSteppingNumbers(low: number, high: number): number[] {
3    // Initializing an array to store the stepping numbers.
4    const steppingNumbers: number[] = [];
5
6    // If low is 0, we include it as it's technically a stepping number.
7    if (low === 0) {
8        steppingNumbers.push(0);
9    }
10
11    // Initialize a queue to perform breadth-first search.
12    const queue: number[] = [];
13
14    // Seed the queue with numbers 1 through 9, the single-digit stepping numbers.
15    for (let digit = 1; digit < 10; ++digit) {
16        queue.push(digit);
17    }
18
19    // Execute breadth-first search to find all stepping numbers up to 'high'.
20    while (queue.length) {
21        // Fetch the first number in queue.
22        const currentNum = queue.shift()!;
23      
24        // Stop processing if the current number exceeds the high bound.
25        if (currentNum > high) {
26            break;
27        }
28      
29        // If the current number is within the range, add it to the result.
30        if (currentNum >= low) {
31            steppingNumbers.push(currentNum);
32        }
33
34        // Check the last digit of the current number.
35        const lastDigit = currentNum % 10;
36
37        // If the last digit is not 0, append a valid stepping number by subtracting one.
38        if (lastDigit > 0) {
39            queue.push(currentNum * 10 + lastDigit - 1);
40        }
41
42        // If the last digit is not 9, append a valid stepping number by adding one.
43        if (lastDigit < 9) {
44            queue.push(currentNum * 10 + lastDigit + 1);
45        }
46    }
47
48    // Return the array of stepping numbers found in the range.
49    return steppingNumbers;
50}
51
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

The time complexity of the algorithm is O(10 * 2^log(M)), where M is the highest number you have in the range. Since the algorithm only ever has numbers with up to log(M) digits in the queue and for each such number the algorithm generates at most two more numbers, it ends up with a factor of 2^log(M) operations. Multiplying by the initial range of numbers 1-9 gives us the 10 factor.

The space complexity is O(2^log(M)) because the queue can grow up to include all stepping numbers less than high. The maximum number of elements that the queue can hold is determined by the number of stepping numbers with log(M) digits, which is the number of digits in high. The stepping number sequence grows exponentially as more digits are added to the numbers, and thus the space required by the queue grows exponentially with the number of digits in high, resulting in a space complexity of O(2^log(M)).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫