Is Lexicographical Numbers easy or hard?

Lexicographical Numbers is rated Medium on LeetCode. The difficulty comes from recognizing the implicit trie structure and generating lexicographical order without sorting strings, which requires careful prefix traversal logic.

Lexicographical Numbers Python/Java solution

Python and Java implementations typically follow either DFS recursion or an iterative prefix traversal. Both solutions maintain O(n) time complexity. The iterative version is popular in interviews because it avoids recursion and uses constant extra space.

How to solve Lexicographical Numbers in O(n)?

Treat numbers as prefixes of a virtual trie. Start from 1 and repeatedly go deeper by multiplying by 10 when possible. If not possible, move to the next sibling by incrementing the number, and backtrack by dividing by 10 when the prefix exceeds n. This visits each number once, achieving O(n) time.

What is the best approach for Lexicographical Numbers?

The best approach is iterative lexicographical traversal, which simulates walking through a prefix tree. It generates numbers from 1 to n in dictionary order using arithmetic operations like *10, +1, and /10. This solution runs in O(n) time with O(1) extra space.

Is Lexicographical Numbers asked at Google/Amazon/Meta?

Lexicographical ordering and prefix traversal problems appear in interviews at companies like Google, Amazon, and Meta, especially in questions related to tries or number generation patterns. The problem tests understanding of DFS-style traversal and efficient iteration without sorting.

What data structure is used in Lexicographical Numbers?

The problem conceptually uses a Trie (prefix tree). Each digit extension represents moving to a child node. The DFS approach explicitly mimics trie traversal, while the iterative approach navigates the same structure using arithmetic operations instead of building the tree.

What is the time complexity of Lexicographical Numbers?

Both common solutions run in O(n) time because each number from 1 to n is processed exactly once. The DFS approach uses O(h) auxiliary space for recursion where h is the number of digits in n, while the iterative method uses O(1) extra space.

Description Solution Video 12:44

386. Lexicographical Numbers

Medium76.2% acceptance6 companies

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 * 10⁴

Asked at 6 companies

Bloomberg Barclays

Google Amazon Microsoft Meta

Topics

Depth-First Search Trie

12:44

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def lexicalOrder(self, n: int) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution