Lexicographical numbers

Depth-First Search Trie

76.2% acceptance

Jan 12, 2026

3125

214

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order. You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn lexical_order(n: i32) -> Vec<i32> {
    let mut result = Vec::with_capacity(n as usize);
    let mut current = 1;
    
    for _ in 0..n {
      result.push(current);
      
      if current * 10 <= n {
        current *= 10;
      } else {
        while current % 10 == 9 || current + 1 > n {
          current /= 10;
        }
        current += 1;
      }
    }
    
    result
  }
}