Lexicographical Numbers

main.md

Question

Approach

I thought of the numbers as forming a tree — where each node represents a number, and its children are formed by appending digits 0 through 9. I used a pre-order traversal approach to explore this virtual tree. I started with 1, and at each step, I either moved deeper by multiplying the number by 10 or incremented to the next number. If the current number ended with 9 or the next number exceeded n, I backtracked by dividing the number until I found a valid next sibling.

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:
                while curr % 10 == 9 or curr + 1 > n:
                    curr //= 10
                curr += 1
        return res

Complexities

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