Watch 4 video solutions for Stepping Numbers, a medium level problem involving Math, Backtracking, Breadth-First Search. This walkthrough by Binod Suman Academy has 2,213 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.
321 is a stepping number while 421 is not.Given two integers low and high, return a sorted list of all the stepping numbers in the inclusive range [low, high].
Example 1:
Input: low = 0, high = 21 Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]
Example 2:
Input: low = 10, high = 15 Output: [10,12]
Constraints:
0 <= low <= high <= 2 * 109Problem Overview: A stepping number is an integer where the absolute difference between every pair of adjacent digits is exactly 1. Given a range [low, high], return all numbers in that interval that satisfy this property. The challenge is generating valid numbers efficiently without checking every integer in the range.
Approach 1: Brute Force Digit Check (O(n * d) time, O(1) space)
The most direct method iterates through every number from low to high. For each number, convert it to digits and check whether the absolute difference between adjacent digits equals 1. This requires scanning up to d digits per number, giving O(n * d) time where n is the range size. The approach is simple but inefficient when the range is large because most numbers will fail the stepping condition.
Approach 2: Backtracking / DFS Generation (O(k) time, O(k) space)
Instead of checking every number, generate only valid stepping numbers using depth‑first search. Start with digits 1 through 9. For each number, append the next digit as lastDigit ± 1. This guarantees the stepping property while constructing the number. Stop recursion once the number exceeds high. The algorithm produces only valid candidates, so the time complexity becomes proportional to the number of generated stepping numbers k. DFS is a natural fit when you think of the problem as exploring a digit tree with two possible branches per node.
Approach 3: Breadth‑First Search (O(k) time, O(k) space)
The optimal and most common solution uses Breadth‑First Search. Initialize a queue with digits 1 through 9. Repeatedly pop a number, add it to the result if it lies in [low, high], and expand it by appending digits derived from lastDigit ± 1. Because BFS grows numbers level by level, it naturally generates stepping numbers in increasing order. This avoids scanning invalid numbers and keeps the complexity proportional to the number of valid results k. The idea is similar to exploring a graph where each node represents a number and edges connect numbers whose last digits differ by one.
The problem mixes digit manipulation with graph traversal concepts. Many candidates recognize the pattern once they think about generating numbers rather than validating them. Related ideas often appear in problems involving digit construction with constraints, which combine backtracking and math reasoning.
Recommended for interviews: BFS generation. It avoids unnecessary checks and demonstrates that you can model the problem as state expansion instead of brute‑force iteration. Mentioning the brute‑force check first shows you understand the definition of stepping numbers, but switching to BFS highlights stronger algorithmic thinking and leads to an efficient O(k) solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Check | O(n * d) | O(1) | Simple implementation when the range size is very small |
| Backtracking / DFS Generation | O(k) | O(k) | When you prefer recursive exploration of digit combinations |
| Breadth-First Search (BFS) | O(k) | O(k) | Best general solution; generates stepping numbers directly in increasing order |