Problem Statement in English
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
Lexicographical order is the way strings are sorted alphabetically. For example, lexicographically, “apple” comes before “banana”.
In this case, 10 would come before 2, because $1$ is lexicographically less than $2$. Similarly, $12$ would come before $2$.
Approach
The idea is that we move the digit to the left and try all numbers from 0 to 9 in the empty space generated.
We can do this with a recursive function - basically Depth First Search.
Solution in Python
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
# list to store the answer
ans = []
# recursive call
def dfs(next: int):
# if the next number is greater than n
# we must discard this pathway
if next > n:
return
# if the next number is not 0
if next != 0:
# add it to the answer
ans.append(next)
# if the next number multiplied by 10 is less than n
# that means we can move it to the left by 1 digit
# and try all numbers from 0 to 9,
# in the now empty space
if next * 10 < n:
# move to the left by 1 digit
next *= 10
# try all numbers from 0 to 9
# in the now empty space
for i in range(10):
# if the next number is greater than 0
if next + i > 0:
# recursive call
dfs(next + i)
# initial call
dfs(0)
# return final answer
return ans
Complexity
Time: $O(n)$
Since we only process $n$ numbers at most.Space: $O(n)$
Since we store $n$ numbers in the answer list.
And we are done.