Stepping Numbers - Solution & Explanation

Problem 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.