Stepping Numbers solution and explanation
9 more videos on this problem
Stepping Numbers | InterviewBit | Geeksforgeeks | HindiLeetforces · 8:24 · 6K views
Stepping Numbers | What is Stepping number and how to Generate | Leetcode #1215 | Live CodeBinod Suman Academy · 17:18 · 2K views
Day 113 - Stepping Numbers | BFS-DFS | GFG POTD 23 OctSagar Malhotra · 22:32 · 2K views
Stepping Numbers | Problem of the Day: 23/10/22 | Abhinav AwasthiSchool of AI · 24:06 · 986 views
Stepping Numbers | BFS,DFS | GFG POTD 23 Oct | D-02 | GraphsAkshay Anil · 27:30 · 967 views
Stepping Numbers || GeeksforGeeks || POTDTechWithSaumya · 15:28 · 856 views
Leetcode 1215. Stepping Numbers (bfs)LetsCode · 11:55 · 190 views
Stepping Numbers | GFG | Amazon | FAANG | Easy Solution | Problem of the day | Naive & Optimal(DFS)Big-O(1) 💻 · 4:37 · 174 views
LeetCode Medium: 1215. Stepping Numbersrobzingcod · 8:58 · 81 views
Stepping Numbers || JAVA Code || C++ Code || GeeksForGeeks || POTD || Digit DP || Log(n) || Hindi ||Code - गुरू · 23:37 · 67 views
The problem
A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.
- For example,
321is a stepping number while421is 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 * 109
Approach overview
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.
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.
class Solution:
def countSteppingNumbers(self, low: int, high: int) -> List[int]:
ans = []
if low == 0:
ans.append(0)
q = deque(range(1, 10))
while q:
v = q.popleft()
if v > high:
break
if v >= low:
ans.append(v)
x = v % 10
if x:
q.append(v * 10 + x - 1)
if x < 9:
q.append(v * 10 + x + 1)
return ansclass Solution {
public List<Integer> countSteppingNumbers(int low, int high) {
List<Integer> ans = new ArrayList<>();
if (low == 0) {
ans.add(0);
}
Deque<Long> q = new ArrayDeque<>();
for (long i = 1; i < 10; ++i) {
q.offer(i);
}
while (!q.isEmpty()) {
long v = q.pollFirst();
if (v > high) {
break;
}
if (v >= low) {
ans.add((int) v);
}
int x = (int) v % 10;
if (x > 0) {
q.offer(v * 10 + x - 1);
}
if (x < 9) {
q.offer(v * 10 + x + 1);
}
}
return ans;
}
}class Solution {
public:
vector<int> countSteppingNumbers(int low, int high) {
vector<int> ans;
if (low == 0) {
ans.push_back(0);
}
queue<long long> q;
for (int i = 1; i < 10; ++i) {
q.push(i);
}
while (!q.empty()) {
long long v = q.front();
q.pop();
if (v > high) {
break;
}
if (v >= low) {
ans.push_back(v);
}
int x = v % 10;
if (x > 0) {
q.push(v * 10 + x - 1);
}
if (x < 9) {
q.push(v * 10 + x + 1);
}
}
return ans;
}
};function countSteppingNumbers(low: number, high: number): number[] {
const ans: number[] = [];
if (low === 0) {
ans.push(0);
}
const q: number[] = [];
for (let i = 1; i < 10; ++i) {
q.push(i);
}
while (q.length) {
const v = q.shift()!;
if (v > high) {
break;
}
if (v >= low) {
ans.push(v);
}
const x = v % 10;
if (x > 0) {
q.push(v * 10 + x - 1);
}
if (x < 9) {
q.push(v * 10 + x + 1);
}
}
return ans;
}func countSteppingNumbers(low int, high int) []int {
ans := []int{}
if low == 0 {
ans = append(ans, 0)
}
q := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
for len(q) > 0 {
v := q[0]
q = q[1:]
if v > high {
break
}
if v >= low {
ans = append(ans, v)
}
x := v % 10
if x > 0 {
q = append(q, v*10+x-1)
}
if x < 9 {
q = append(q, v*10+x+1)
}
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
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.