Lexicographical Numbers - Solution & Explanation
Problem Statement
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.
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]
Constraints:
1 <= n <= 5 * 104
Approach Overview
Problem Overview: Given an integer n, return the numbers from 1 to n sorted in lexicographical (dictionary) order. The challenge is generating this order without converting all numbers to strings and sorting them, which would add unnecessary overhead.
Approach 1: DFS Prefix Traversal (O(n) time, O(h) space)
This problem maps naturally to a Trie-like prefix tree. Each number is treated as a prefix, and its children are formed by appending digits 0-9. Starting from prefixes 1 through 9, perform a depth-first traversal and keep expanding by multiplying the current number by 10 and adding digits. If the generated value exceeds n, stop exploring that branch. This produces numbers exactly in lexicographical order because DFS always explores the smallest prefix first.
The recursion depth corresponds to the number of digits in n, making the auxiliary space O(h) where h ≈ log10(n). This method is conceptually simple and mirrors how a Trie organizes numbers by prefixes. It’s also a clean application of Depth-First Search.
Approach 2: Iterative Lexicographical Traversal (O(n) time, O(1) space)
The iterative solution simulates the same prefix traversal without recursion. Start with current = 1. At each step, append the current number to the result. If current * 10 ≤ n, move to the smallest child (go deeper in the prefix tree). Otherwise, move to the next sibling by incrementing current. If the increment causes a trailing zero boundary or exceeds n, repeatedly divide by 10 until a valid next prefix is found.
This logic mimics walking through an implicit trie in lexicographical order. Instead of storing the tree, you navigate it using arithmetic operations like *10, +1, and /10. Every number from 1 to n is visited exactly once, giving O(n) time complexity while keeping extra space constant.
Recommended for interviews: Interviewers typically expect the iterative prefix traversal. It demonstrates understanding of lexicographical ordering and avoids recursion overhead, achieving O(n) time and O(1) extra space. The DFS approach is still valuable because it clearly shows the underlying trie structure and confirms your understanding of the traversal pattern.
Approach 1: DFS Approach
The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.
This C implementation uses a helper function dfs to execute the depth-first search. It explores each tree node by multiplying the current number by 10 and adding digits from 0 to 9, ensuring the number remains within the limit n. The results are stored in an array which is printed in the main function.
Complexity
Time Complexity: O(n), Space Complexity: O(1) (excluding the output array).
Approach 2: Iterative Approach
This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.
This C code leverages a simple iterative method to achieve lexical order. By multiplying the current index by 10, or adjusting on digit boundaries, this code manages to efficiently iterate through lexical numbers.
Complexity
Time Complexity: O(n), Space Complexity: O(1) (ignoring return array).
Approach 3: Iteration
We first define a variable v, initially v = 1. Then we start iterating from 1, adding v to the answer array each time. Then, if v times 10 leq n, we update v to v times 10; otherwise, if v bmod 10 = 9 or v + 1 > n, we loop to divide v by 10. After the loop ends, we increment v. Continue iterating until we have added n numbers to the answer array.
The time complexity is O(n), where n is the given integer n. Ignoring the space consumption of the answer array, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| DFS Approach | Time Complexity: O(n), Space Complexity: O(1) (excluding the output array). |
| Iterative Approach | Time Complexity: O(n), Space Complexity: O(1) (ignoring return array). |
| Iteration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Prefix Traversal | O(n) | O(h) recursion stack | When you want a clear conceptual mapping to a trie or DFS traversal of prefixes |
| Iterative Lexicographical Traversal | O(n) | O(1) extra space | Preferred for interviews and production due to constant space and direct traversal |
Video Solution
Lexicographical Numbers - Leetcode 386 - Python • NeetCodeIO • 20,401 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Lexicographical Numbers easy or hard?
Lexicographical Numbers Python/Java solution
How to solve Lexicographical Numbers in O(n)?
What is the best approach for Lexicographical Numbers?
Is Lexicographical Numbers asked at Google/Amazon/Meta?
What data structure is used in Lexicographical Numbers?
What is the time complexity of Lexicographical Numbers?
Ready to solve this problem?
Practice Lexicographical Numbers with our built-in code editor and test cases.
Practice on FleetCode