Problem statement
A stepping number has adjacent decimal digits whose absolute difference is exactly 1. 123 and 210 qualify; 11 and 349 do not. Every one-digit number qualifies because it has no adjacent pair to violate the rule.
Return all stepping numbers in inclusive [low, high], sorted increasingly. The original takeUforward prompt permits 0≤low≤high≤2,000,000,000.
For [0,21], return [0,1,2,3,4,5,6,7,8,9,10,12,21]. We are solving list generation, not the separate “Count Stepping Numbers in Range” large-bound digit-DP problem.
Constraints & requirements
- CONTRACT
- Return the actual sorted numbers, not just their count; do not include duplicates.
Examples 3 test cases
Example 1 Case 1
- Input
low=0; high=21- Output
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21]
Zero is saved once and final order is sorted.
Example 2 Case 2
- Input
low=10; high=13- Output
[10, 12]
Both boundaries are inclusive.
Example 3 Case 3
- Input
low=11; high=11- Output
[]
Equal adjacent digits do not step.
Hints Optional
01Find the smaller problem
For a number ending in digit d, how many legal next digits are there?
02Define the state
Only d−1 and d+1, bounded by 0 and 9. Start from digits 1–9; handle zero once.
03Connect the recurrence
Prune above high, keep growing below low, use long for children, and sort the DFS output.
How to think before coding
Treat a number as a prefix. Its last digit d permits only d−1 and d+1 as children, if those digits stay in 0..9. Keep extending a number below low because a descendant can enter the range; stop above high because descendants only grow. Add zero separately, start other roots at 1..9, and sort the DFS output if increasing order is required.
Baseline: check every integer
static boolean isStepping(int value) {
while (value >= 10) { // Single-digit remainder has no pair left to check.
int last = value % 10; // Read the rightmost digit.
int previous = (value / 10) % 10; // Read its neighbor.
if (Math.abs(last - previous) != 1) return false; // Reject one bad adjacent pair.
value /= 10; // Remove the digit whose pair was checked.
}
return true; // Every pair satisfied the rule; zero also qualifies.
}For a range containing R integers with at most D digits, scanning costs O(RD), plus output storage. With a range reaching two billion, this is unnecessary work.
Intuition: append only a legal next digit
If the current number ends in d, its next digit can only be d−1 or d+1. From 12, build 121 or 123. From 10, only 101 is legal; −1 is not a digit. From 9, only 98 is legal; 10 is not a digit.
Start positive trees at 1–9. Handle zero separately. Starting a tree at zero would create leading-zero representations and duplicate ordinary numbers.
A number smaller than low must still be extended: 1 is below low=100, but 101 may be in range. A number above high can stop: appending a digit to a positive number only increases it.
DFS generation and sorted output
Handle zero separately, keep extending below low, and widen arithmetic before appending digits. A 1 grows to 10 and 12, never 11. The DFS result is sorted explicitly; the BFS illustration shows how a queue visits the same digit-generation tree in a different order.
public static List<Integer> steppingNumbers(int low, int high) {
List<Integer> answer = new ArrayList<>(); // Collect generated values that lie in the range.
if (low == 0) answer.add(0); // Include zero once; never extend it into leading-zero numbers.
for (int first = 1; first <= 9; first++) { // Each positive number has one nonzero first digit.
extendStepping(first, low, high, answer); // Explore the tree rooted at that first digit.
}
Collections.sort(answer); // DFS order is not numeric order across roots or depths.
return answer; // Return the sorted list, not its count.
}
private static void extendStepping(long number, int low, int high, List<Integer> answer) {
if (number > high) return; // Appending a digit only increases this positive number.
if (number >= low) answer.add((int) number); // Save this prefix only when it is in range.
int last = (int) (number % 10); // Only the final digit constrains the next digit.
if (last > 0) { // A digit below zero does not exist.
extendStepping(number * 10 + last - 1, low, high, answer); // Append last-1 using long.
}
if (last < 9) { // A digit above nine does not exist.
extendStepping(number * 10 + last + 1, low, high, answer); // Append last+1 using long.
}
}Why long for number? high fits int, but a child calculated before the bound check can exceed int. Multiplication must happen in long before any cast.
Why sort? DFS may produce 1,10,101 before visiting root 2. That is valid traversal order, not increasing numerical order. Sorting the collected in-range results fulfills the contract.
Recursion forest: roots and pruning
For high=21, root 1 creates:
1 → save ├─ 10 → save │ └─ 101 → above 21; prune └─ 12 → save ├─ 121 → above 21; prune └─ 123 → above 21; prune 2 → save ├─ 21 → save │ ├─ 210 → above 21; prune │ └─ 212 → above 21; prune └─ 23 → above 21; prune roots 3..9 are explored similarly 0 is saved separately, not expanded
This is a forest of nine recursive roots, not one fabricated include/exclude tree. The outer loop is the driver; it is not another recursive child in this forest.
Dry run

Read the text transcript
| Current number | Decision | Why |
|---|---|---|
| 0 | Save separately if low=0 | Avoid leading-zero duplicates |
| 1 | Save if in range; grow 10,12 | Last digit 1 has two neighbors |
| 10 | Grow 101 only | Last digit 0 has no −1 neighbor |
| 101 | Return without saving | Exceeds high=21 |
| 2 | Grow 21,23 | Digits differ by one |
| 23 | Prune | Too large |
| Finished | Sort results | DFS order is not numeric order |
Why this is correct
Every generated root is a valid one-digit positive number. Every extension uses an adjacent digit differing by one, so it remains valid. Every positive stepping number has a unique first digit and a unique sequence of legal appended digits; therefore it is generated once. Pruning above high cannot discard an in-range descendant. Zero is handled once.
Complexity
Let V be the number of generated recursive calls, including the just-over-bound children; M the number of in-range results; D the maximum digit depth. Generation costs O(V), sorting costs O(M log M), and auxiliary recursion space is O(D), plus O(M) result/sort storage.
A loose generation bound is O(9·2ᴰ), since each node has at most two children. Actual branching is smaller at digits 0 and 9. Avoid O(high−low) for this generator, and avoid claiming O(M) when low is high: it still explores prefixes below low.
BFS with a queue is also natural. Seeds in increasing order and lower child first can generate numeric order, but its frontier uses more memory; DFS plus sorting keeps the recursive explanation simple.
Mistakes and tests
- Growing zero creates duplicates or unhelpful zero paths.
- Pruning number<low misses valid descendants.
- Casting after overflowing an int does not fix the overflow.
- Returning the DFS sequence without sorting violates the problem.
- [0,0] → [0]; [10,13] → [10,12]; [11,11] → []; [98,101] → [98,101].
- Test the upper limit near 2,000,000,000 using long intermediate arithmetic.
Recognition and related practice
“When digits obey a local rule and the numerical range is huge,” generate candidates from valid prefixes. Compare binary-string generation, where the previous digit also controls the next choice.
Company evidence
Amazon · historical candidate report. A Code360 Amazon SDE-1 experience by PREETAM associates a 26 October 2021 round with generating a sorted list of stepping numbers in a range. This is a user-submitted account, not an official frequency claim; the search-index text was available but direct retrieval was restricted. Research checked 3 October 2026.
Final takeaway
Do not search every number. Grow only legal digit prefixes, stop above the upper bound, and sort the saved results.
Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.
Practice next
Next lessonSplit a BST in Java: Return Two Trees Without Rebuilding ThemCompare a different recursive promise and how its parent resumes.