Lexicographical Numbers — DSA · Engineering Playbook

Problem#

Given an integer n, return all numbers from 1 to n in lexicographic order. The solution must run in O(n) time and use O(1) extra space.

Examples#

n = 13 → [1,10,11,12,13,2,3,4,5,6,7,8,9].
n = 2 → [1,2].

Constraints#

1 <= n <= 5 * 10^4.

Hints#

Hint

Think of an implicit 10-ary tree rooted at 0 with children cur*10 + d. Pre-order it.

Approach#

Iterative pre-order over a virtual digit trie. From cur, try multiplying by 10 (descend). If cur * 10 > n, increment and back up past trailing 9s as needed.

Solution#

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        ans.reserve(n);
        int cur = 1;
        for (int i = 0; i < n; ++i) {
            ans.push_back(cur);
            if ((long long)cur * 10 <= n) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) cur /= 10;
                ++cur;
            }
        }
        return ans;
    }
};

func lexicalOrder(n int) []int {
    ans := make([]int, 0, n)
    cur := 1
    for i := 0; i < n; i++ {
        ans = append(ans, cur)
        if cur*10 <= n {
            cur *= 10
        } else {
            for cur%10 == 9 || cur+1 > n {
                cur /= 10
            }
            cur++
        }
    }
    return ans
}

from typing import List

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans: List[int] = []
        cur = 1
        for _ in range(n):
            ans.append(cur)
            if cur * 10 <= n:
                cur *= 10
            else:
                while cur % 10 == 9 or cur + 1 > n:
                    cur //= 10
                cur += 1
        return ans

function lexicalOrder(n) {
    const ans = [];
    let cur = 1;
    for (let i = 0; i < n; i++) {
        ans.push(cur);
        if (cur * 10 <= n) {
            cur *= 10;
        } else {
            while (cur % 10 === 9 || cur + 1 > n) cur = Math.floor(cur / 10);
            cur++;
        }
    }
    return ans;
}

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        int cur = 1;
        for (int i = 0; i < n; i++) {
            ans.add(cur);
            if ((long) cur * 10 <= n) {
                cur *= 10;
            } else {
                while (cur % 10 == 9 || cur + 1 > n) cur /= 10;
                cur++;
            }
        }
        return ans;
    }
}

function lexicalOrder(n: number): number[] {
    const ans: number[] = [];
    let cur = 1;
    for (let i = 0; i < n; i++) {
        ans.push(cur);
        if (cur * 10 <= n) {
            cur *= 10;
        } else {
            while (cur % 10 === 9 || cur + 1 > n) cur = Math.floor(cur / 10);
            cur++;
        }
    }
    return ans;
}

Editorial#

Numbers in lexicographic order are exactly the pre-order traversal of the digit trie (root 0, children 1..9 at root, 0..9 at deeper nodes). At each step, the “next” lexicographic number is cur * 10 if it fits, otherwise cur + 1 after rolling up trailing 9s. The long long cast guards overflow when cur approaches INT_MAX / 10.

Complexity#

Time: O(n).
Space: O(1) extra (excluding output).

Concept revision#

K-th Smallest in Lexicographical Order

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#