386. Lexicographical Numbers

Depth-First Search Trie Stack Backtracking

Time: O(n)

Space: O(1)

Intuition

Lexicographic order is DFS traversal of a 10-ary trie (each node 0 - 9 as children). Start from 1, go as deep as possible (multiply by 10), backtrack when needed (increment + skip trailing 9s and divisors of 10).

Algorithm

1curr=1, result=[].
2For i from 1 to n: append curr to result.
3If curr*10 <= n: curr *= 10.
4Else: if curr >= n: curr /= 10. curr++. While curr % 10 == 0: curr /= 10.

Example Walkthrough

Input: n = 13

1.1->10->11->12->13->(backtrack)->2->3->...->9.
2.Order: 1,10,11,12,13,2,3,4,5,6,7,8,9.

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

Common Pitfalls

•After backtracking, keep dividing by 10 while the number ends in 0 to maintain valid prefix form.

386.cs

// Approach: Simulate a preorder DFS on a decimal trie: multiply by 10 to
// descend a level, then increment by 1 to move to the next sibling.
// Time: O(n) Space: O(1)

public class Solution
{
    public IList<int> LexicalOrder(int n)
    {
        // Initialize a List to store the lexicographically ordered numbers
        List<int> result = new List<int>();
        // Start with the smallest lexicographically number 1
        int current = 1;

        for (int i = 0; i < n; ++i)
        {
            // Add the current number to the result list
            result.Add(current);

            // Check if the next lexicographical step is to multiply by 10
            if (current * 10 <= n)
                current *= 10; // If so, go down one level of the lexical tree
            else
            {
                // If reached the end of this lexical level (e.g., n is 13 and current is 9),
                // or the increment leads past n, go up one level and increment
                while (current % 10 == 9 || current + 1 > n)
                    current /= 10;
                current++; // Increment to the next number in lexical order
            }
        }

        // Return the list containing the lexicographically ordered numbers
        return result;
    }
}

Was this solution helpful?