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.
First, if low is 0, we need to add 0 to the answer.
Next, we create a queue q and add 1 \sim 9 to the queue. Then, we repeatedly take out elements from the queue. Let the current element be v. If v is greater than high, we stop searching. If v is in the range [low, high], we add v to the answer. Then, we need to record the last digit of v as x. If x \gt 0, we add v times 10 + x - 1 to the queue. If x \lt 9, we add v times 10 + x + 1 to the queue. Repeat the above steps until the queue is empty.
The time complexity is O(10 times 2^{log M}), and the space complexity is O(2^{log M}), where M is the number of digits in high.
Python
Java
C++
Go
TypeScript
| 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 |
Stepping Numbers | What is Stepping number and how to Generate | Leetcode #1215 | Live Code • Binod Suman Academy • 2,213 views views
Watch 3 more video solutions →Practice Stepping Numbers with our built-in code editor and test cases.
Practice on FleetCode