386.Lexicographical_Numbers(Medium).md

386. Lexicographical Numbers (Medium)

Date and Time: Oct 16, 2024, 21:49 (EST)

Link: https://leetcode.com/problems/lexicographical-numbers/

Question:

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 * 10^4

Walk-through:

We know we start from curr = 1, then we try to reach curr *= 10 to be the most significant, then we can start adding curr += 1 when curr < n, then if we encounter curr >= n, we start shrinking curr //= 10, so we can now increment its second to the last digit.

Python Solution:

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        # Repeatedly increment curr
        # We first increment curr *= 10, so we can start dfs
        # When curr > n or last digit of curr is 9, we curr //= 10
        curr = 1
        res = []
        # Ensure we have n elements in res
        for _ in range(n):
            res.append(curr)
            if curr * 10 <= n:
                curr *= 10
            else:
                while curr + 1 > n or curr % 10 == 9:
                    curr //= 10
                curr += 1
        return res

Time Complexity: $O(n)$
Space Complexity: $O(1)$