Stepping Numbers

Stepping Numbers

What is this problem about?

A Stepping Number is an integer such that all its adjacent digits have an absolute difference of exactly 1. For example, 321 and 456 are stepping numbers, while 135 is not. The Stepping Numbers coding problem asks you to find all stepping numbers in a given range [low, high].

Why is this asked in interviews?

Asked by Epic Systems, this problem tests your ability to generate numbers that follow a specific pattern. It assesses whether you can use Breadth-First Search (BFS) or Backtracking to explore a state space efficiently. It's a great test of your understanding of how numbers are constructed digit by digit and your ability to prune searches that fall outside the given range.

Algorithmic pattern used

Both BFS and Backtracking are suitable.

• BFS approach: Start by pushing digits 1-9 into a queue. For each number $X$ in the queue, find its last digit $D$. If $D > 0$, you can form a new stepping number $X \cdot 10 + (D-1)$. If $D < 9$, you can form $X \cdot 10 + (D+1)$. If the new number is within the range, add it to your results. If it's less than high, push it back into the queue for further expansion.
• DFS/Backtracking: Similar logic, but exploring as deep as possible before moving to the next starting digit.

Example explanation (use your own example)

Let's find stepping numbers starting with 2:

• 2 is a stepping number.
• From 2, we can form 21 and 23.
• From 21, we can form 210 and 212.
• From 23, we can form 232 and 234.
• From 210, we can only form 2101 (since $0-1$ is invalid). We repeat this for all starting digits 1-9. Zero is also a stepping number if the range includes it.

Common mistakes candidates make

• Sorting: Generating numbers in an arbitrary order and then having to sort the entire list.
• Range errors: Including numbers that are larger than high or missing the number 0.
• Leading zeros: Incorrectly generating numbers like "01" which is just 1.
• Inefficiency: Checking every single number from low to high to see if it's a stepping number, which is extremely slow if the range is large.

Interview preparation tip

For Math and state-space search problems, generating valid candidates is almost always better than filtering a large range. This Stepping Numbers interview question is a classic "generation vs. filtration" scenario.