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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Lexicographical Numbers and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →