Numbers with same consecutive differences

Backtracking Breadth-First Search

59.1% acceptance

Feb 25, 2026

2881

200

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order. Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn nums_same_consec_diff(n: i32, k: i32) -> Vec<i32> {
    let mut res = Vec::new();
    if n == 1 { return (0..=9).collect(); }
    let mut stack: Vec<i32> = (1..=9).collect();
    while let Some(num) = stack.pop() {
      let last = num % 10;
      let digits = num.to_string().len() as i32;
      if digits == n { res.push(num); continue; }
      if last + k <= 9 { stack.push(num * 10 + last + k); }
      if k != 0 && last - k >= 0 { stack.push(num * 10 + last - k); }
    }
    res.sort();
    res
  }
}