Lexicographical Numbers Python Solution

Tested Python solution for LeetCode 386 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 386, Medium. Topics: Depth-First Search, Trie. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 386   # by problem number
lcpy gen -s lexicographical_numbers   # by problem name

​

Problem

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.

​

Examples

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

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

​

Constraints

• 1 <= n <= 5 * 10^4

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n)
    # Space: O(1)
    def lexical_order(self, n: int) -> list[int]:
        result: list[int] = []
        curr = 1
        for _ in range(n):
            result.append(curr)
            if curr * 10 <= n:
                curr *= 10
            else:
                while curr % 10 == 9 or curr + 1 > n:
                    curr //= 10
                curr += 1
        return result

​

Complexity

Time	Space
O(n)	O(1)

​

Tags

NeetCode All.