LeetCode 386: Lexicographical Numbers Solution in Python – A Step-by-Step Guide

What Is LeetCode 386: Lexicographical Numbers?

LeetCode 386: Lexicographical Numbers gives you an integer n, and your task is to return all numbers from 1 to n in lexicographical order—where numbers are treated as strings and sorted alphabetically (e.g., "10" comes before "2"). It’s a problem that tests your ability to generate and order numbers efficiently based on their string representation!

Problem Statement

• Input:
• n: Integer representing the upper bound (1 to n).
• Output: List[int] - Numbers from 1 to n in lexicographical order.
• Rules:
• Order numbers as strings (e.g., "1", "10", "2").
• Include all integers from 1 to n inclusive.

Constraints

• 1 <= n <= 5 * 10⁴

Examples

• Input: n = 13
• Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
• Lex order: "1", "10", "11", "12", "13", "2", "3", ...
• Input: n = 2
• Output: [1,2]
• Lex order: "1", "2".
• Input: n = 10
• Output: [1,10,2,3,4,5,6,7,8,9]
• Lex order: "1", "10", "2", ...

These show the dictionary-like order—let’s solve it!

Understanding the Problem: Lexicographical Ordering

To tackle LeetCode 386 in Python, we need to: 1. Generate all numbers from 1 to n. 2. Order them lexicographically (as strings). 3. Do so efficiently given n’s potential size.

A naive approach might generate all numbers and sort them as strings, but that’s O(n log n). We’ll use:

• Best Solution: Depth-first search—O(n) time, O(1) extra space—fast and optimal.
• Alternative Solution: Iterative counting—O(n log n) time, O(n) space—intuitive but slower.

Let’s order with the best solution!

Best Solution: Depth-First Search (DFS)

Why This Is the Best Solution

The DFS approach runs in O(n) time with O(1) extra space (excluding output) by exploring numbers in a tree-like manner, starting with digits 1-9 and appending 0-9 recursively, pruning when exceeding n. It’s the most efficient—generating numbers in lexicographical order naturally without sorting, leveraging the prefix structure of numbers!

How It Works

Think of it like a number tree:

• Start: Begin with digits 1-9 (no leading zeros).
• DFS: For each number:
• Add to result if ≤ n.
• Recursively try appending 0-9 (e.g., 1 → 10, 11, ...).
• Stop if number exceeds n.
• Result: List in lex order.

It’s like growing a tree of numbers, branch by branch!

Step-by-Step Example

For n = 13:

• Start: Result = [].
• DFS(1):
• Add 1, Result = [1].
• DFS(10): Add 10, Result = [1, 10].
• DFS(11): Add 11, Result = [1, 10, 11].
• DFS(12): Add 12, Result = [1, 10, 11, 12].
• DFS(13): Add 13, Result = [1, 10, 11, 12, 13].
• DFS(14): > 13, stop.
• DFS(2): Add 2, Result = [1, 10, 11, 12, 13, 2].
• DFS(20): > 13, stop.
• DFS(3): Add 3, Result = [1, 10, 11, 12, 13, 2, 3].
• ...: Continue to 9.
• Result: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9].

For n = 2:

• DFS(1): Add 1, DFS(10) > 2, stop.
• DFS(2): Add 2.
• Result: [1, 2].

Code with Explanation

Here’s the Python code using DFS:

Copy codeclass Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []

        # DFS helper to explore numbers
        def dfs(curr, n):
            if curr > n:
                return
            result.append(curr)
            # Try appending 0-9
            for i in range(10):
                next_num = curr * 10 + i
                if next_num > n:
                    break
                dfs(next_num, n)

        # Start with digits 1-9
        for i in range(1, 10):
            dfs(i, n)

        return result

Explanation

• Line 4: result: List to store numbers.
• Lines 6-15: dfs(curr, n):
• If curr > n, stop—O(1).
• Add curr to result—O(1).
• Try appending 0-9, recurse if ≤ n—O(10) per call.
• Lines 17-18: Start DFS with 1-9—O(1) per start.
• Time: O(n)—generates n numbers, each step O(1) amortized.
• Space: O(1)—excluding output, recursion stack is O(log n).

This is like a number tree explorer—fast and ordered!

Alternative Solution: Iterative Counting

Why an Alternative Approach?

The iterative counting solution runs in O(n log n) time with O(n) space by generating all numbers from 1 to n and sorting them lexicographically as strings. It’s less efficient—great for understanding a brute-force approach, though slower and memory-heavy compared to DFS!

How It Works

• Generate: Create list of 1 to n.
• Sort: Sort as strings using lexicographical order.
• Convert: Convert back to integers.
• Result: Return sorted list.

Step-by-Step Example

For n = 13:

• Generate: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].
• Sort as Strings: ["1", "10", "11", "12", "13", "2", "3", "4", "5", "6", "7", "8", "9"].
• Convert: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9].
• Result: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9].

For n = 2:

• Generate: [1, 2].
• Sort: ["1", "2"].
• Result: [1, 2].

Code with Explanation

Copy codeclass Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        # Generate numbers 1 to n
        numbers = list(range(1, n + 1))

        # Sort lexicographically as strings
        numbers.sort(key=str)

        return numbers

Explanation

• Line 4: numbers: List of 1 to n—O(n).
• Line 6: Sort using str key—O(n log n).
• Line 8: Return sorted list—O(1).
• Time: O(n log n)—sorting dominates.
• Space: O(n)—stores all numbers.

It’s a straightforward sorter—simple but slow!

Comparing the Two Solutions

• DFS (Best):
• Time: O(n)—linear generation.
• Space: O(1)—minimal extra space.
• Pros: Fast, space-efficient, natural order.
• Cons: Recursive logic.
• Iterative Counting (Alternative):
• Time: O(n log n)—sorting.
• Space: O(n)—array.
• Pros: Simple, intuitive.
• Cons: Slower, more memory.

DFS wins for speed and efficiency!

Additional Examples and Edge Cases

• n=1: [1] (both work).
• n=100: DFS scales linearly, sorting lags.
• Large n: DFS avoids sorting overhead.

DFS is superior, iterative works but slower.

Complexity Breakdown

• DFS:
• Time: O(n).
• Space: O(1).
• Iterative Counting:
• Time: O(n log n).
• Space: O(n).

DFS excels for performance.

Key Takeaways

• DFS: Grow numbers—fast and lean!
• Iterative Counting: Sort numbers—clear but slow!
• Lex Order: Strings guide numbers.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Order Those Numbers

LeetCode 386: Lexicographical Numbers in Python is an ordering challenge. DFS is the efficiency champ, while iterative counting offers a simpler but slower alternative. Want more? Try LeetCode 46: Permutations or LeetCode 332: Reconstruct Itinerary. Ready to sort? Visit Solve LeetCode 386 on LeetCode and list those numbers today!