Naive Solution

A naive solution would involve generating all numbers from 1 to n, converting them to strings, sorting the strings lexicographically, and then converting them back to integers. This approach is simple to understand but not efficient.

Code (Python):

def lexicalOrder_naive(n):
    nums = list(range(1, n + 1))
    nums_str = [str(num) for num in nums]
    nums_str.sort()
    result = [int(num_str) for num_str in nums_str]
    return result

Time Complexity: O(n log n) due to the sorting step.

Space Complexity: O(n) to store the numbers and their string representations.

Optimal Solution

A more efficient approach is to use Depth-First Search (DFS) to generate the numbers in lexicographical order. We start with 1, then generate its children (10, 11, 12, ...), and so on, as long as the numbers are within the range [1, n].

Algorithm:

1. Initialize an empty list result to store the numbers in lexicographical order.
2. Define a recursive function dfs(num, n, result):
   • Add num to the result list.
   • Iterate from 0 to 9:
     • Calculate next_num = num * 10 + i.
     • If next_num is within the range [1, n], call dfs(next_num, n, result).
3. Start the DFS from 1.

Code (Python):

def lexicalOrder(n):
    result = []
    
    def dfs(num, n, result):
        if num > n:
            return
        
        result.append(num)
        
        for i in range(10):
            next_num = num * 10 + i
            if next_num > 0 and next_num <= n:
                dfs(next_num, n, result)
    
    for i in range(1, min(10, n + 1)):
        dfs(i, n, result)
    return result

# Iterative version
def lexicalOrder_iterative(n):
    result = []
    curr = 1
    for _ in range(n):
        result.append(curr)
        if curr * 10 <= n:
            curr *= 10
        else:
            if curr >= n:
                curr //= 10
            curr += 1
            while curr % 10 == 0:
                curr //= 10
                
    return result

Time Complexity: O(n). Each number is visited exactly once.

Space Complexity: O(1) excluding the output list. The recursive calls use stack space, but in the iterative version it is O(1).

Edge Cases:

• n = 0: The problem statement specifies 1 <= n <= 5 * 10^4, so this case is invalid. However, returning [] would be a reasonable approach if it were allowed.
• n = 1: The result should be [1].
• n = 9: The result should be [1, 2, 3, 4, 5, 6, 7, 8, 9].
• n = 10: The result should be [1, 10, 2, 3, 4, 5, 6, 7, 8, 9].