# 1215. Stepping Numbers    ## Approach 1: BFS

• Time: $O(|\texttt{ans}|)$
• Space: $O(|\texttt{ans}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector countSteppingNumbers(int low, int high) { vector ans; if (low == 0) ans.push_back(0); queue q; for (int i = 1; i <= 9; ++i) q.push(i); while (!q.empty()) { const long curr = q.front(); q.pop(); if (curr > high) continue; if (curr >= low) ans.push_back(curr); const int lastDigit = curr % 10; if (lastDigit > 0) q.push(curr * 10 + lastDigit - 1); if (lastDigit < 9) q.push(curr * 10 + lastDigit + 1); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public List countSteppingNumbers(int low, int high) { List ans = new ArrayList<>(); if (low == 0) ans.add(0); Queue q = new ArrayDeque<>(); for (long i = 1; i <= 9; ++i) q.offer(i); while (!q.isEmpty()) { final long curr = q.poll(); if (curr > high) continue; if (curr >= low) ans.add((int) curr); final long lastDigit = curr % 10; if (lastDigit > 0) q.offer(curr * 10 + lastDigit - 1); if (lastDigit < 9) q.offer(curr * 10 + lastDigit + 1); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def countSteppingNumbers(self, low: int, high: int) -> List[int]: ans =  if low == 0 else [] q = collections.deque(list(range(1, 10))) while q: curr = q.popleft() if curr > high: continue if curr >= low: ans.append(curr) lastDigit = curr % 10 if lastDigit > 0: q.append(curr * 10 + lastDigit - 1) if lastDigit < 9: q.append(curr * 10 + lastDigit + 1) return ans 

## Approach 2: DFS

• Time: $O(\texttt{sort}(\texttt{ans}))$
• Space: $O(|\texttt{ans}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: vector countSteppingNumbers(int low, int high) { vector ans; if (low == 0) ans.push_back(0); for (int i = 1; i <= 9; ++i) dfs(i, low, high, ans); sort(begin(ans), end(ans)); return ans; } private: void dfs(long curr, int low, int high, vector& ans) { if (curr > high) return; if (curr >= low) ans.push_back(curr); const int lastDigit = curr % 10; if (lastDigit > 0) dfs(curr * 10 + lastDigit - 1, low, high, ans); if (lastDigit < 9) dfs(curr * 10 + lastDigit + 1, low, high, ans); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public List countSteppingNumbers(int low, int high) { List ans = new ArrayList<>(); if (low == 0) ans.add(0); for (long i = 1; i <= 9; ++i) dfs(i, low, high, ans); Collections.sort(ans); return ans; } private void dfs(long curr, int low, int high, List ans) { if (curr > high) return; if (curr >= low) ans.add((int) curr); final long lastDigit = curr % 10; if (lastDigit > 0) dfs(curr * 10 + lastDigit - 1, low, high, ans); if (lastDigit < 9) dfs(curr * 10 + lastDigit + 1, low, high, ans); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def countSteppingNumbers(self, low: int, high: int) -> List[int]: ans =  if low == 0 else [] def dfs(curr: int) -> None: if curr > high: return if curr >= low: ans.append(curr) lastDigit = curr % 10 if lastDigit > 0: dfs(curr * 10 + lastDigit - 1) if lastDigit < 9: dfs(curr * 10 + lastDigit + 1) for i in range(1, 9 + 1): dfs(i) ans.sort() return ans