LeetCode Entry

386. Lexicographical Numbers

08.06.2025 medium 2025 kotlin rust

Generate lexicographical numbers 1..n

386. Lexicographical Numbers medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1013

Problem TLDR

Generate lexicographical numbers 1..n #medium

Intuition

    // 1 10 100 1000 11 12 120 2 20 200 21

There is a DFS pattern in the order: 1, 2, 3 are the headers, with fillers in-between.

Approach

• the iterative variant is clever: go deep by *10, then increment, then remove all zeros
• by rewriting the order, some interesting implementations are possible, like runningFold/scan

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

// 22ms
    fun lexicalOrder(n: Int) = buildList<Int> {
        var x = 1
        repeat(n) {
            add(x)
            if (x * 10 <= n) x *= 10
            else {
                if (x == n) x /= 10
                x++
                while (x % 10 == 0) x /= 10
            }
        }
    }

// 19ms
    fun lexicalOrder(n: Int) = buildList<Int> {
        fun dfs(p: Int) {
            if (p > n) return@dfs
            add(p); for (d in 0..9) dfs(p * 10 + d)
        }
        for (d in 1..9) dfs(d)
    }

// 18ms
    fun lexicalOrder(n: Int) =
        (1..<n).runningFold(1) { r, t -> var x = r
            if (x * 10 <= n) x *= 10
            else {
                if (x == n) x /= 10
                x++
                while (x % 10 == 0) x /= 10
            }
            x
        }

// 6ms
    fun lexicalOrder(n: Int): List<Int> {
        var x = 0
        return List<Int>(n) {
            if (x > 0 && x * 10 <= n) x *= 10
            else {
                if (x == n) x /= 10
                x++
                while (x % 10 == 0) x /= 10
            }
            x
        }
    }

// 0ms
    pub fn lexical_order(n: i32) -> Vec<i32> {
        (0..n).scan(0, |x, t| {
            if *x > 0 && *x * 10 <= n { *x *= 10 }
            else {
                if *x == n { *x /= 10 }
                *x += 1;
                while *x % 10 == 0 { *x /= 10 }
            }; Some(*x)
        }).collect()
    }

// 1ms
    vector<int> lexicalOrder(int n) {
        int x = 1; vector<int>r(n);
        for (int i = 0; i < n; ++i) {
            r[i] = x;
            if (x * 10 <= n) x *= 10;
            else {
                if (x == n) x /= 10;
                ++x;
                while (x % 10 == 0) x /= 10;
            }
        } return r;
    }