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 . - 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
0is 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 handlelow = 0explicitly if we don’t generate from seed 0 (since extending 0 creates invalid representations). - The upper bound is , 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 ( iterations 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: where is number of digits (). With , this results in roughly 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 () until exceeding
high. This reduces our search space to only valid candidates.
Approach
- Initialization: Create a list to store results. Handle the number
0separately if it falls within[low, high], as we cannot generate multi-digit stepping numbers starting from seed0(leading zeros are invalid). - DFS Generation: Define a recursive function that takes the current number and its last digit.
- If the current number is
high, add it to our results list. - Calculate potential next digits:
last_digit - 1andlast_digit + 1. - Recursively call DFS for valid next digits (must be between 0-9).
- If the current number is
- Seeds: Start the recursion with single-digit seeds from to .
- Filtering & Sorting: Since we generate all stepping numbers , filter those that are also at the end, then sort the list numerically before returning.
Complexity Analysis
- Time Complexity: Let be the count of valid stepping numbers up to
high. The DFS visits each valid number once and performs constant work per digit (). Sorting takes . Thus, total time is roughly proportional to generating all candidates plus sorting: . Given the constraints, is small (thousands), making this highly efficient compared to brute force. - Space Complexity: for recursion stack depth ( digits). Plus 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 ifhigh >= 0and adds0to results since single digit numbers are stepping numbers.- Single Digit Range: If range is
[5, 6], seeds generate them; filtering ensures only valid ones remain. - No Stepping Numbers in Range: Returns empty list (handled naturally by logic).
- Max Value Constraint (): DFS prunes branches exceeding
highimmediately, preventing overflow or excessive computation.