Given an integer n, return the numbers 1 to n arranged in lexicographic
(dictionary) order, where numbers are compared as strings.
lexicalOrder(n)
Input format: a single integer n. Output the numbers space-separated.
n=13 // → 1 10 11 12 13 2 3 4 5 6 7 8 9
n=2 // → 1 2
The brute-force approach: generate 1 through n, convert to strings, sort. That works but costs O(n log n) for the sort plus string overhead — more than needed for what's actually a structured ordering.
Lexicographic order compares numbers as strings. "1" is a prefix of "10"–"19", which are prefixes of "100"–"109", "110"–"119", and so on. Appending a digit produces a more specific string that still starts with the original — a tree, where each number's children are itself with one more digit (0–9) appended. The root level is 1 through 9 (no leading zeros).
"1" comes before "10", before "100", before "11" — visit a number, then everything prefixed by it, before moving to the next sibling. That's exactly pre-order DFS: visit the node, recurse fully into each child in digit order, then return to the next sibling.
The traversal visits each number once, already in order — no sort needed. Total work is O(n), not O(n log n). Some orderings that look like they need an explicit sort are actually implicit in a natural tree structure — spot that, and a simple traversal replaces the sort.
def lexical_order(n):
res = []
def dfs(cur):
if cur > n:
return
res.append(cur)
for d in range(10):
nxt = cur * 10 + d
if nxt > n:
break
dfs(nxt)
for start in range(1, 10):
if start > n:
break
dfs(start)
return res
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.