Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Lexicographical order groups numbers by their decimal prefixes. After 1 comes 10 when it exists, and only after all numbers beginning with 1 do we visit 2. This is a preorder walk through an implicit prefix tree, which can be navigated with arithmetic instead of a stored tree or recursion stack.

Approach

Start at one and append the current number to the result.
If multiplying it by ten stays within n, descend to its first child.
Otherwise, look for a next sibling. While the last digit is nine or incrementing would exceed n, remove the last digit to move up a level. Then increment the remaining prefix.
Repeat exactly n times. This emits every integer once in prefix order; any candidate computed after the last emission is unused.

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        res = []
        curr = 1

        for i in range(1, n + 1):
            res.append(curr)
            if curr * 10 <= n:
                curr *= 10
            else:
                while curr % 10 == 9 or curr + 1 > n:
                    curr //= 10
                curr += 1

        return res

Complexity analysis

The code performs a preorder walk of the implicit decimal-prefix tree and emits each value once. It uses O(n) time and O(1) auxiliary space beyond the O(n) returned array.