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]

Works fine from 1 - 99

def lexicalOrder(self, n: int) -> List[int]:
    ls = []

    def callthis(i):
        k = i
        while i <= n:
            ls.append(i)
            i = int(str(k) + '0')

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

    return ls

Optimised:

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

        for _ in range(n):
            result.append(current)
            if current * 10 <= n:
                current *= 10  # Go deeper in lexicographical tree
            else:
                if current >= n:
                    current //= 10  # Go back up if out of range
                current += 1
                while current % 10 == 0:
                    current //= 10  # Skip trailing zeros

        return result