Skip to content

386. Lexicographical Numbers

Solve in Leetcode

Description

Static Badge

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.

Example 1

  • Input: n = 13
  • Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2

  • Input: n = 2
  • Output: [1,2]

Constraints

  • 1 <= 5 <= 104

Solution: Iterative

First, we start from 1 and keep multiplying by 10 and incrementing by 1 until it exceeds n. When it exceeds n, we divide it by 10 and get the leading digits and increment it by 1 to get the next number.

  • Time Complexity: O(n),
    • n is the input number
    • Not O(n2) even thought it contains while inside for loop, because while is not dependent on n and it bounds with 10 at max which is constant. As long as it bounded by a constant or a small function (like O(k) for some constant k), it still considered as O(n) even though it might takes longer execution time.
  • Space Complexity: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function lexicalOrder(n: number): number[] {
    const numbers: number[] = [];
    let current = 1;

    for (let i = 0; i < n; i++) {
        numbers.push(current);

        if (current * 10 <= n) {
            current *= 10;
        } else {
            while (current % 10 == 9 || current >= n) {
                current = Math.trunc(current / 10);
            }

            current += 1;
        }
    }

    return numbers;
};

We use trie1 or a prefix tree which . We can use trie to store the lexicographical order of numbers from 1 to n.

  • Time Complexity: O(n),
    • We vist each node from 1 to n once, therefore it depends on the number of nodes in the trie which is the input number n
  • Space Complexity: O(log10​(n))
    • We store the numbers from 1 to n in the result array which is O(n)
    • We also have recursive call stack which depends on numbers from 1 to n. If n has d digits, the recursive call stack will be O(d) which similar to O(log10(n))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function lexicalOrder(n: number): number[] {

    // Backtracking
    const result: number[] = []


    function _dfs(node: number) {
        /// Stop if node is greater than n
        if (node > n) return;

        /// Visit the node
        result.push(node)

        for (let i = 0; i <= 9; i++) {
            _dfs(node * 10 + i);
        }
    }

    for (let i = 1; i <= 9; i++) {
        _dfs(i);
    }

    return result;
};

  1. Trie is a tree data structure that stores a dynamic set of strings. Tries are commonly used to store the entire English language for quick prefix lookups. The term trie comes from the word retrieval, but is pronounced "try" to distinguish it from other "tree" structures. ↩