Skip to main content

386. Lexicographical Numbers

medium

Return numbers 1..n in lexicographical order. Pre-order DFS over the implicit decimal tree — each node has up to 10 children (digit appends).

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order. You must write an algorithm that runs in O(n) time and uses O(1) extra space (the result array does not count).

Constraints

  • 1 <= n <= 5 * 10^4

Examples

Example 1

Input
n = 13
Output
[1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2

Input
n = 2
Output
[1,2]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Think of numbers 1..n as a 10-ary tree where root has children 1..9 and every other node n has children n*10, n*10+1, ..., n*10+9.

Hint 2

DFS pre-order: visit node, then recurse into each child whose value <= n.

Hint 3

Start DFS from each of 1..9.

Hint 4

Iterative version: maintain a current number; advance lexicographically (cur*10 if <= n, else step up and add 1).

Solution approach

Reveal approach

Pre-order DFS over the implicit decimal tree. Start: for start in 1..9, if start <= n, dfs(start). dfs(cur): if cur > n, return. Append cur to result. For i in 0..9: next = cur * 10 + i; if next > n, return; dfs(next). The DFS visits each integer in [1, n] exactly once in lex order. Time O(n). Space O(log n) for recursion depth. Iterative O(1)-space version: track cur = 1, push to result, then advance: if cur * 10 <= n, cur *= 10; else if cur % 10 != 9 and cur + 1 <= n, cur += 1; else while cur > 0 and (cur % 10 == 9 or cur + 1 > n), cur /= 10; cur += 1. Repeat n times.

Complexity

Time
O(n)
Space
O(log n)

Related patterns

  • recursion
  • dfs
  • trie-implicit

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Bytedance
  • Amazon

More Recursion practice problems

See all Recursion problems →