386. Lexicographical Numbers

2026, Mar 07 One min read

1. Description

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.

2. Example

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]

3. Constraints

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

4. Solutions

Depth-First Search

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    vector<int> lexicalOrder(const int n) {
        vector<int> numbers(n);
        int num = 1;
        for (int i = 0; i < n; ++i) {
            numbers[i] = num;

            if (num * 10 <= n) {
                num *= 10;
            } else {
                while (num % 9 == 0 || num >= n) {
                    num /= 10;
                }

                ++num;
            }
        }

        return numbers;
    }
};