Naive Approach: Sorting

A straightforward approach is to generate all numbers from 1 to n, convert them to strings, and then sort the strings lexicographically. Finally, convert the sorted strings back to integers.

Algorithm:

1. Create a list of numbers from 1 to n.
2. Convert each number to a string.
3. Sort the list of strings lexicographically.
4. Convert the sorted strings back to integers.

Code:

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 operation.

Space Complexity:

• O(n) - to store the numbers as strings.

Optimal Approach: Depth-First Search (DFS)

A more efficient approach is to use Depth-First Search (DFS) to generate the numbers in lexicographical order directly. We can think of this as traversing a n-ary tree where each node's children are its multiples of 10.

Algorithm:

1. Start with the number 1.
2. Add it to the result list.
3. Recursively explore its children (10, 11, 12, ..., up to a limit based on n).
4. If multiplying by 10 exceeds n, backtrack and try incrementing the current number until it is less than 10.
5. Repeat until all numbers in the range [1, n] have been added.

Code:

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

# An iterative solution:

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) - We are using a constant amount of extra space (excluding the output list).

Edge Cases:

• n = 0: The problem states 1 <= n <= 5 * 10^4, so n=0 is not a valid input
• n = 1: Should return [1]
• n = 9: Should return [1,2,3,4,5,6,7,8,9]
• n = 10: Should return [1,10,2,3,4,5,6,7,8,9]
• Large n (e.g., 50000): The algorithm should handle large values of n efficiently without exceeding memory limits or execution time limits.