Domain 2MediumMEDIUM

Stepping Numbers

LeetCode problem 1215: Stepping Numbers (medium).

Domain: medium•Updated: 2026-09-10
#Backtracking

Problem Breakdown

We need to identify integers between low and high (inclusive) where every adjacent pair of digits differs by exactly 1 in absolute value.

  • Inputs: Two non-negative integers low, high. Max range is 2⋅1092 \cdot 10^9.
  • Outputs: A sorted list of valid stepping numbers within the range.
  • Edge Cases & Constraints:
    • Single-digit numbers (e.g., 5) are always stepping numbers because there are no adjacent digits to violate the condition.
    • The number 0 is a valid stepping number, but it cannot be extended into multi-digit numbers like “01” due to leading zero constraints in standard integer representation logic for this problem type. We must handle low = 0 explicitly if we don’t generate from seed 0 (since extending 0 creates invalid representations).
    • The upper bound is 2⋅1092 \cdot 10^9, meaning numbers can have up to 10 digits. This fits within standard integer limits, but brute-forcing every number in the range will time out (O(High)O(High) iterations ×\times digit check cost).

Intuition

A naive approach would iterate through every integer from low to high, convert each to a string or extract digits mathematically, and verify the stepping condition.

  • Brute Force Complexity: O((High−Low)⋅D)O((High - Low) \cdot D) where DD is number of digits (≈10\approx 10). With High=2⋅109High = 2 \cdot 10^9, this results in roughly 2×10102 \times 10^{10} operations, which will exceed time limits.
  • Key Insight: Stepping numbers are sparse within the range. Instead of checking every number, we can construct them digit by digit using Depth First Search (DFS). We start with single-digit seeds and recursively append valid next digits (d±1d \pm 1) until exceeding high. This reduces our search space to only valid candidates.

Approach

  1. Initialization: Create a list to store results. Handle the number 0 separately if it falls within [low, high], as we cannot generate multi-digit stepping numbers starting from seed 0 (leading zeros are invalid).
  2. DFS Generation: Define a recursive function that takes the current number and its last digit.
    • If the current number is ≤\le high, add it to our results list.
    • Calculate potential next digits: last_digit - 1 and last_digit + 1.
    • Recursively call DFS for valid next digits (must be between 0-9).
  3. Seeds: Start the recursion with single-digit seeds from 11 to 99.
  4. Filtering & Sorting: Since we generate all stepping numbers ≤high\le high, filter those that are also ≥low\ge low at the end, then sort the list numerically before returning.

Complexity Analysis

  • Time Complexity: Let KK be the count of valid stepping numbers up to high. The DFS visits each valid number once and performs constant work per digit (O(D)O(D)). Sorting takes O(Klog⁡K)O(K \log K). Thus, total time is roughly proportional to generating all candidates plus sorting: O(K+Davg⋅K+Klog⁡K)O(K + D_{avg} \cdot K + K \log K). Given the constraints, KK is small (thousands), making this highly efficient compared to brute force.
  • Space Complexity: O(D)O(D) for recursion stack depth (D≈10D \approx 10 digits). Plus O(K)O(K) space to store the result list.

Solution

from typing import List

def steppingNumbers(low: int, high: int) -> List[int]:
    res = []
    
    # Helper DFS function to generate numbers digit by digit
    def dfs(curr_num):
        if curr_num > high:
            return
        
        # Add valid number (we filter low/high later or during generation logic 
        # but here we collect all <= high and sort/filter at end for simplicity)
        res.append(curr_num)
        
        last_digit = curr_num % 10
        
        # Try appending next digit - 1
        if last_digit > 0:
            dfs(curr_num * 10 + (last_digit - 1))
            
        # Try appending next digit + 1
        if last_digit < 9:
            dfs(curr_num * 10 + (last_digit + 1))

    # Start DFS with single digits 1-9. 
    # We handle '0' separately because it cannot be a parent of multi-digit numbers
    for i in range(1, 10):
        if high >= i:
            dfs(i)
            
    # Handle the number 0 specifically as it is valid but not generated by seeds 1-9
    if low <= 0 and high >= 0:
        res.append(0)

    # Filter based on lower bound (in case we added numbers < low during generation logic 
    # though our DFS prunes >high, so only need to check >=low here for the '0' or others? 
    # Actually dfs adds everything <= high. We must filter by low.)
    
    res = [num for num in res if num >= low]
    
    return sorted(res)

# Example usage:
# print(steppingNumbers(0, 21)) -> Output: [0, 1, ..., 9, 10, 12, 21]

Edge Cases Handled

  • low = 0: Explicitly checks if high >= 0 and adds 0 to results since single digit numbers are stepping numbers.
  • Single Digit Range: If range is [5, 6], seeds 1..91..9 generate them; filtering ensures only valid ones remain.
  • No Stepping Numbers in Range: Returns empty list (handled naturally by logic).
  • Max Value Constraint (2⋅1092 \cdot 10^9): DFS prunes branches exceeding high immediately, preventing overflow or excessive computation.