Stepping Numbers - Leetcode Solution

Problem Statement:

A stepping number is a number where every digit is either one more or one less than the previous digit. Examples include 123, 232, and 21. Given two integers low and high, find all the stepping numbers in the range [low, high].

Solution:

This problem can be solved using a BFS approach. We keep a queue to store the candidate stepping numbers and a list to store the final solution.

Firstly, we add all the single digit numbers from 0 to 9 in the queue as they are already stepping numbers.

Then, we begin the BFS by popping the first number from the queue, checking if it falls in the range [low, high], and adding it to the solution list if it does.

Next, we get the last digit of the current number and calculate the next possible digits by adding or subtracting 1 from it. If the next digit is less than or equal to 9 and greater than or equal to 0, we add the next stepping number obtained by appending the next digit to the current number to the queue.

For example, for the number 123, the next possible digits are 2 and 4. So, the next stepping numbers would be 1232 and 1234.

We repeat this process until the queue becomes empty.

Code:

Here is the Python code to solve the problem:

class Solution: def countSteppingNumbers(self, low: int, high: int) -> List[int]:

    # Adds single digit numbers to queue as they are stepping numbers
    queue = [i for i in range(10)]
    # Stores the final solution
    res = []
    
    # BFS approach
    while queue:
        num = queue.pop(0)
        # If number falls in range, add it to the solution
        if num >= low and num <= high:
            res.append(num)
        if num == 0 or num > high:
            continue
        # Get the last digit of the number
        last_digit = num % 10
        # Calculate next possible digits by adding or subtracting 1 
        next_digits = set([last_digit - 1, last_digit + 1])
        # Add new stepping numbers obtained by appending next digit to current number to queue
        for digit in next_digits:
            if digit >= 0 and digit <= 9:
                new_num = num * 10 + digit
                queue.append(new_num)
    
    # Sort and return the solution
    res.sort()
    return res

Time Complexity:

The time complexity of this solution is O(N), where N is the number of stepping numbers between low and high. This is because we are checking every possible stepping number in the range using a BFS approach.

Space Complexity:

The space complexity of this solution is O(2^N + K), where N is the maximum possible length of a stepping number and K is the number of stepping numbers between low and high. This is because we are storing the stepping numbers in the queue and solution list, which can take up to 2^N space. Additionally, we are storing the final solution in the res list, which takes up K space.

1