NUHMAN.com

📘 Problem Statement

Given an integer n, return all the numbers in the range [1, n] in lexicographical order.

• Lexicographical order is similar to the order of words in a dictionary. For example, for n = 20, the lexicographical order is:

csharp

[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9]

📚 Example:

python

Input:
n = 20
Output:
[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9]

🧠 Key Insight

This problem involves generating numbers in lexicographical order, which can be thought of as a depth-first search (DFS) problem. We can treat the numbers as nodes in a tree, where each node has a child node that is the number formed by appending a digit from 0-9.

For example:

• Start with 1, and explore its children: 10, 11, ..., 19.
• Once we reach a number greater than n, backtrack and explore the next sibling node (2, 3, etc.).

💡 Approach

1. Recursive DFS Approach:

• Start from 1, and at each step, append digits to the current number.
• If the current number is less than or equal to n, add it to the result and recurse by appending digits 0-9 to it.
• Once the current number exceeds n, stop recursing further down that path.

1. Backtracking:

• Once all numbers starting from a digit have been processed, backtrack to explore the next possible number.

1. Edge Case:

• If n is less than 1, return an empty list.

🐍 Python Code

python

class Solution:
    def lexicalOrder(self, n: int):
        """
        Generate numbers in lexicographical order from 1 to n.
        """
        result = []
        
        def dfs(current):
            # If the current number exceeds n, stop recursion
            if current > n:
                return
            result.append(current)
            # Try appending digits 0-9 to the current number
            for i in range(10):
                new_num = current * 10 + i
                if new_num > n:
                    break  # No need to go further if new number exceeds n
                dfs(new_num)
        
        # Start DFS with numbers 1 to 9
        for i in range(1, 10):
            dfs(i)
        
        return result

🔍 Step-by-Step Explanation

1. Initialization (lexicalOrder Method)

python

def lexicalOrder(self, n: int):
    result = []

• We initialize an empty list result to store the final lexicographically ordered numbers.

2. DFS Function

python

def dfs(current):
    if current > n:
        return
    result.append(current)
    for i in range(10):
        new_num = current * 10 + i
        if new_num > n:
            break
        dfs(new_num)

• dfs(current): This is a recursive function that takes the current number as input.
• If current > n, we stop recursion (base case).
• We append the current number to result.
• We then try appending digits 0-9 to current to form new numbers. If the new number is valid (i.e., less than or equal to n), we recurse further with the new number.
• If new_num > n, we stop appending further digits, as any number formed will exceed n.

3. Iterating from 1 to 9

python

for i in range(1, 10):
    dfs(i)

• We start the DFS from 1 to 9, as these are the possible starting digits of numbers in lexicographical order.

4. Return Result

python

return result

• Finally, we return the result list containing all numbers in lexicographical order from 1 to n.

💡 Example Walkthrough

Example 1:

python

Input:
n = 20
Output:
[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9]

1. Start DFS:

• Start with 1: Append 1 to the result. Try digits 0-9, but stop once we exceed 20.
• Explore 10 → 11 → 12 → 13 → 14 → 15 → 16 → 17 → 18 → 19.

1. Backtrack:

• After exploring 1, backtrack to explore 2, 3, ..., 9.

1. Final Result:

• The lexicographical order of numbers from 1 to 20 is [1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9].

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

• Time Complexity:
• The algorithm recursively explores all valid numbers from 1 to n. Each valid number is added to the result exactly once, so the time complexity is O(n).
• Space Complexity:
• The space complexity is O(n) since we store the result list, which contains up to n numbers.

🧵 Final Thoughts

LeetCode 386 offers a fascinating exercise in generating numbers in lexicographical order using depth-first search (DFS). This approach efficiently generates numbers in the desired order without the need to manually sort them. It's a great example of how recursion and backtracking can be used to solve problems related to number generation in a structured order.

The solution is efficient both in time and space, and it’s a great demonstration of recursive algorithms in Python.