Tags: "leetcode", "trie", access_time 1-min read

# Lexicographical Numbers

#### Created: February 16, 2020 by [lek-tin]

##### Last updated: February 16, 2020

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: `[1,10,11,12,13,2,3,4,5,6,7,8,9]`.

Please optimize your algorithm to use less time and space. The input size may be as large as `5,000,000`.

### Solution (iterative)

``````class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = [0 for i in range(n)]

curr = 1

for i in range(n):
res[i] = curr
# lower digits
if curr * 10 <= n:
curr *= 10
# higher digits
else:
# if curr is greater than n, we reverse it by /10
if curr >= n:
curr //= 10
curr += 1
# if curr becomes X00000, we need to get rid of the trailing 0's
while curr % 10 == 0:
curr //= 10

return res
# Input: n = 50
# Output: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,6,7,8,9]
``````

### Solution (recursion)

Recursion

``````class Solution:
def lexicalOrder(self, n: int) -> List[int]:
res = [0 for i in range(n)]
for i in range(10):
self.helper(i, n, res)
return res

def helper(self, curr, n, res):
if curr > n:
return

res.append(curr)

for i in range(10):
if curr*10 + i <= n:
self.helper(curr*10+i, n, res)
else:
break
``````