Stepping numbers

Math Backtracking Breadth-First Search

48.3% acceptance

Mar 31, 2026

188

No description available.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_stepping_numbers(low: i32, high: i32) -> Vec<i32> {
    let mut result = Vec::new();
    let mut queue = std::collections::VecDeque::new();
    if low <= 0 {
      result.push(0);
    }
    for d in 1..=9i64 {
      queue.push_back(d);
    }
    while let Some(num) = queue.pop_front() {
      if num > high as i64 { continue; }
      if num >= low as i64 {
        result.push(num as i32);
      }
      let last = num % 10;
      if last > 0 {
        let next = num * 10 + last - 1;
        if next <= high as i64 {
          queue.push_back(next);
        }
      }
      if last < 9 {
        let next = num * 10 + last + 1;
        if next <= high as i64 {
          queue.push_back(next);
        }
      }
    }
    result.sort();
    result
  }
}