Is Stepping Numbers easy or hard?

Stepping Numbers is generally considered a medium difficulty problem. The definition is simple, but the efficient solution requires recognizing that you should generate valid numbers with BFS or DFS rather than checking every integer in the range.

Stepping Numbers Python/Java solution

Most implementations follow the same BFS pattern across languages. Initialize a queue with digits 1–9, pop numbers, add them to the result if they fall within the range, and push new numbers formed by lastDigit ± 1. The logic remains identical in Python, Java, C++, Go, and TypeScript.

How to solve Stepping Numbers in O(n)?

Instead of checking every number in the interval, generate stepping numbers directly. Use BFS starting from digits 1–9 and append digits equal to lastDigit ± 1. Stop expanding when the number exceeds the upper bound. The algorithm effectively runs in O(k) time, proportional to the number of valid results.

What is the best approach for Stepping Numbers?

Breadth‑First Search (BFS) is the most practical approach. Start with digits 1–9 in a queue and repeatedly append lastDigit ± 1 to build new numbers. This generates only valid stepping numbers and avoids scanning the entire range. The complexity is O(k), where k is the number of stepping numbers produced.

Is Stepping Numbers asked at Google/Amazon/Meta?

Digit‑generation problems like Stepping Numbers appear in interviews at large tech companies because they test BFS/DFS thinking and number manipulation. Variants involving digit constraints or graph-style number generation have been reported in Amazon and Google interview preparation sets.

What data structure is used in Stepping Numbers?

A queue is used for the BFS solution. Each queue element represents a partially built stepping number. By expanding the last digit with ±1 transitions, the queue acts like a graph traversal over valid digit states.

What is the time complexity of Stepping Numbers?

The optimal BFS or DFS generation approach runs in O(k) time, where k is the number of valid stepping numbers within the range. Each generated number is processed once and expanded into at most two new candidates. Space complexity is also O(k) due to the queue or recursion stack.

Description Hints 3 Solution Video 8:24

1215. Stepping Numbers

Medium48.2% acceptance1 companyPremium elsewhere, free here

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.

For example, 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 * 10⁹

Asked at 1 company

Epic Systems

Topics

Hints open one at a time

Hint 1

Try to generate the numbers using recursion.

Hint 2

In one step in the recursion, add a valid digit to the right of the current number.

Hint 3

Save the number if it's in the range between low and high.

8:24

Still stuck?Read the written solution, or watch a walkthrough.

Open solution