386. Lexicographical Numbers

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

You must write an algorithm that runs in O(n) time and uses O(1) extra space. 

Example 1:

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

Example 2:

Input: n = 2
Output: [1,2]

Constraints:

• 1 <= n <= 5 * 104

Approach 01:

class Solution {
public:
    vector<int> lexicalOrder(int maxNumber) {
        vector<int> result;
        int currentNumber = 1;

        // Generate numbers in lexicographical order
        while (result.size() < maxNumber) {
            result.push_back(currentNumber);
            if (currentNumber * 10 <= maxNumber) {
                currentNumber *= 10;
            } else {
                while (currentNumber % 10 == 9 || currentNumber == maxNumber)
                    currentNumber /= 10;
                ++currentNumber;
            }
        }

        return result;
    }
};

class Solution:
    def lexicalOrder(self, maxNumber: int) -> list[int]:
        result = []
        currentNumber = 1

        # Generate numbers in lexicographical order
        while len(result) < maxNumber:
            result.append(currentNumber)
            if currentNumber * 10 <= maxNumber:
                currentNumber *= 10
            else:
                while currentNumber % 10 == 9 or currentNumber == maxNumber:
                    currentNumber //= 10
                currentNumber += 1

        return result

Time Complexity

• Generating Numbers:

  The function generates numbers in lexicographical order up to maxNumber. Since we are generating exactly maxNumber numbers, the number of iterations through the while loop will be \(O(\text{maxNumber})\).

• Handling Each Number:

  In each iteration, either the number is multiplied by 10 or the number is divided by 10 and incremented. These operations are constant time \(O(1)\), so the overall time complexity is linear in terms of the number of generated numbers.

• Overall Time Complexity:

  The overall time complexity is \(O(\text{maxNumber})\).

Space Complexity

• Space for Result Vector:

  The result vector stores maxNumber integers, so the space complexity for storing the result is \(O(\text{maxNumber})\).

• Overall Space Complexity:

  The overall space complexity is \(O(\text{maxNumber})\) due to the space needed for the result vector.