We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stepping Numbers

Number: 1151

Difficulty: Medium

Paid? Yes

Companies: Epic Systems

Problem Description

Given two integers low and high, find and return a sorted list of all stepping numbers in the inclusive range [low, high]. A stepping number is an integer in which the absolute difference between every pair of adjacent digits is exactly 1.

Key Insights

  • A stepping number has the property that for each adjacent pair of digits, their absolute difference is 1.
  • Use a BFS (or DFS/backtracking) approach starting from each digit (0–9) to generate possible stepping number candidates.
  • Special handle for 0 since it is a valid stepping number but does not lead to any larger candidate if used as a starting digit.
  • Stop expanding a branch when the generated number exceeds high.
  • The resulting list should be sorted (BFS approach inherently generates numbers in increasing order, but sorting at the end can be applied as a safeguard).

Space and Time Complexity

Time Complexity: O(2^L) where L is the number of digits in high. In practice, since L is small (at most 10 for high up to 2 * 10^9), the generation is efficient. Space Complexity: O(2^L) due to the BFS queue holding the generated numbers.

Solution

We use Breadth-First Search (BFS) to generate stepping numbers. Begin by adding the digits 0 through 9 (with a special check for 0 because it does not spawn children). For each number popped from the BFS queue, if it is within the range [low, high], add it to the result list. Then compute its last digit; based on that, generate potential next stepping numbers by appending (last_digit - 1) and (last_digit + 1) if they are valid. Continue this process until all possible candidates below or equal to high are generated. Finally, sort and return the result list.

Code Solutions

# Python solution using BFS

from collections import deque

def steppingNumbers(low, high):
    # List to store the stepping numbers within range
    result = []
    
    # Special edge-case: if low is 0, then 0 is a valid stepping number.
    if low == 0:
        result.append(0)
    
    # Initialize BFS queue with digits 1 through 9.
    queue = deque(range(1, 10))
    
    while queue:
        num = queue.popleft()
        # If the current number is within the given range, add it to the result list.
        if low <= num <= high:
            result.append(num)
            
        # If the current number is greater than high, we do not need to expand further.
        if num > high:
            continue
        
        # Get the last digit of the current number.
        last_digit = num % 10
        
        # Determine possible next digits.
        next_digits = set()
        if last_digit > 0:
            next_digits.add(last_digit - 1)
        if last_digit < 9:
            next_digits.add(last_digit + 1)
        
        # Generate the next stepping number and add it to the queue if it does not exceed high.
        for next_digit in next_digits:
            next_num = num * 10 + next_digit
            if next_num <= high:
                queue.append(next_num)
                
    # Return the sorted list of stepping numbers.
    return sorted(result)

# For testing: print the stepping numbers for low = 0 and high = 21.
print(steppingNumbers(0, 21))
← Back to All Questions