Problem statement

https://leetcode.com/problems/lexicographical-numbers/

Solution

We can solve it in O(n) time and space if we use backtracking: for each number k, we check than numbers 10k, ..., 10k + 9 less than n. When we met number more than n, we break.

Complexity

So, for every number 1, ... , n we check at most one number outside our range, and it makes O(n) complexity.

Code

class Solution:
    def lexicalOrder(self, n):
        def dfs(num):     
            self.result.append(num)
            for i in range(1 if num == 0 else 0, 10):
                if num*10 + i > n: break
                dfs(num*10 + i)
                
        self.result = []
        dfs(0)
        return self.result[1:]

Remark

It can be seen as trie problem, but I am not sure that complexity will be O(n) in this case.