Lexicographical Numbers

Lexicographical Numbers

What is this problem about?

The "Lexicographical Numbers interview question" asks you to return all numbers from 1 to n in lexicographical (dictionary) order. For example, if n is 13, the order would be [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]. This "Lexicographical Numbers coding problem" challenges you to generate these numbers without simply sorting them, which would be less efficient.

Why is this asked in interviews?

This problem is popular at companies like Microsoft and Bloomberg because it tests a candidate's understanding of "Depth-First Search interview pattern" and "Trie interview pattern" logic. It requires you to visualize the numbers as a tree structure where each node represents a digit. It evaluates your ability to implement a traversal that visits these "nodes" in a specific order.

Algorithmic pattern used

The primary pattern is Depth-First Search (DFS). Think of the numbers as being organized in a trie where the root is an empty string, and its children are digits 1 through 9. Each node in turn has children 0 through 9. By performing a pre-order traversal on this implicit tree, you can generate the numbers in lexicographical order. You start with 1, then explore 10, 100, etc., before moving back to 11.

Example explanation

Let n = 20.

1. Start with 1.
2. Go to 10 (1 * 10).
3. Go to 100 (too big, skip).
4. Increment 10 to 11.
5. Increment 11 to 12... up to 19.
6. Increment 19. Since it ends in 9, we divide by 10 and then increment. 19 -> 1.9 -> 2.
7. Now at 2. Go to 20. Result: [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20...]

Common mistakes candidates make

• O(n log n) sorting: Using a custom string comparator on a list of numbers. This works but uses extra memory and is slower than the iterative O(n) approach.
• Iterative logic errors: Failing to handle the transition from numbers ending in '9' correctly (need to strip trailing nines and then increment).
• Integer overflow: Not a major risk here since n is usually within 32-bit limits, but always something to consider when multiplying by 10.

Interview preparation tip

Practice visualizing number sequences as tree traversals. The "lexicographical" property is almost always equivalent to a pre-order traversal of a trie or a prefix-based tree.