Solution Explanation: Lexicographical Numbers

This problem asks to generate all numbers from 1 to n in lexicographical order. Lexicographical order is essentially dictionary order; 1 comes before 10, which comes before 11, and so on. A naive approach of sorting would be O(n log n), but the problem explicitly requests an O(n) solution.

The optimal approach utilizes a clever iterative method that avoids explicit sorting. Instead of comparing numbers directly, it cleverly traverses the numbers in lexicographical order by manipulating the current number (v).

Algorithm:

1. Initialization: Start with v = 1. This will be our current number. ans is an empty list to store the results.

2. Iteration: The main loop iterates n times (once for each number).

3. Append to Result: Add the current number v to the ans list.

4. Extend Current Number: If v * 10 is less than or equal to n, it means we can append a '0' to v and still stay within the range [1, n]. So, we multiply v by 10 to extend it lexicographically. (e.g., 1 becomes 10, 2 becomes 20).

5. Increment/Adjust: If we cannot extend v (because v * 10 > n ), we need to adjust it to the next lexicographically larger number. This is done in two steps:

   • Find the next digit: We repeatedly divide v by 10 until we reach a digit that is not 9 or adding 1 would exceed n. This finds the "prefix" where we can increment.
   • Increment and reset: We increment the prefix, then reset the lower-order digits to 0.

6. Return Result: After the loop, ans contains all numbers from 1 to n in lexicographical order.

Time Complexity: O(n)

The algorithm iterates through the numbers from 1 to n exactly once. Each operation within the loop (multiplication, division, addition, comparison) takes constant time. Therefore, the overall time complexity is linear, O(n).

Space Complexity: O(1) (excluding output)

The space used by the algorithm itself is constant. We use a few integer variables (v, i, etc.) and the space used to store the result list ans is not considered part of the algorithm's space complexity according to the problem statement.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript):

The provided code examples in all the specified languages implement this algorithm directly. They all share the same core logic. The differences are primarily syntactic. For example, the core loop in Python looks like this:

for _ in range(n):
    ans.append(v)
    if v * 10 <= n:
        v *= 10
    else:
        while v % 10 == 9 or v + 1 > n:
            v //= 10
        v += 1

The other languages implement essentially the same logic using their respective syntax for loops, integer division, and array/list manipulation.