Problem Description

Given an integer n, return a list of integers from 1 to n in lexicographical (dictionary) order.
For example, if n = 13, the output should be [1,10,11,12,13,2,3,4,5,6,7,8,9].

• You must return the result as a list of integers, not strings.
• Try to write an algorithm that runs in O(n) time and uses O(1) extra space (excluding the output list).
• There is only one valid answer for each input.
• Each number in the result must be unique and within the range 1 to n (inclusive).

Thought Process

At first glance, the problem seems straightforward: generate all numbers from 1 to n, convert them to strings, sort them lexicographically, and convert them back to integers. However, this approach is inefficient:

• Converting integers to strings and back is slow for large n.
• Sorting all the numbers as strings takes O(n log n) time.

Since the problem asks for an O(n) time solution and minimal extra space, we need a different approach. The key is to generate the numbers directly in lexicographical order, without sorting.

This leads us to think recursively or iteratively about how numbers look in lexicographical order, similar to traversing a tree where each node's children are formed by appending digits.

Solution Approach

To generate numbers from 1 to n in lexicographical order efficiently, we can simulate a preorder traversal of a 10-ary tree:

• Each node in the tree represents a number.
• The root nodes are 1 through 9.
• Each node x has up to 10 children: x*10, x*10+1, ..., x*10+9, as long as they do not exceed n.

We start from 1, then go as deep as possible by multiplying by 10 (i.e., 1, 10, 100, ...), then backtrack and increment to the next sibling (i.e., 2, then 20, 200, ...), and so on.

1. Initialize curr = 1.
2. For each step, add curr to the result.
3. If curr * 10 ≤ n, move to curr * 10 (go deeper).
4. Else, if curr % 10 != 9 and curr + 1 ≤ n, increment curr (move to next sibling).
5. Else, backtrack: divide curr by 10 until the last digit is not 9, then increment (move up and right in the tree).
6. Repeat until n numbers are collected.

This approach ensures we visit every number in lexicographical order, without sorting or extra storage.

Example Walkthrough

Let's consider n = 13:

1. Start with 1: add to result.
2. Go deeper: 10 (1 * 10): add to result.
3. Increment: 11 (10 + 1): add to result.
4. Increment: 12 (11 + 1): add to result.
5. Increment: 13 (12 + 1): add to result.
6. Increment: 14 (13 + 1) is greater than 13, so backtrack.
7. Backtrack to 1, increment: 2: add to result.
8. Go deeper: 20 (2 * 10) > 13, so backtrack.
9. Increment: 3: add to result.
10. Repeat similarly for 4, 5, ..., 9.

The output is: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Code Implementation

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

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

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

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

Time and Space Complexity

• Brute-force approach: Convert all numbers to strings, sort, and convert back. This is O(n log n) time due to sorting and O(n) space for the list and the string conversions.
• Optimized approach (tree traversal): Every number from 1 to n is visited once, so the time complexity is O(n). The space complexity is O(1) extra (excluding the output list), since we only use a few variables for traversal.
• This makes the optimized solution highly efficient for large values of n.

Summary

The key insight is to generate numbers in lexicographical order without sorting, by simulating a preorder traversal of a 10-ary tree. This allows us to achieve O(n) time and O(1) extra space, meeting the problem's constraints. The approach is elegant because it leverages the structure of numbers and their string representations, and avoids unnecessary computation.