Leetcode Daily Question 21/09/2024 - 386. Lexicographical Numbers

Problem Description:

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.

from typing import List
class Solution:
  def lexicalOrder(self, n: int) -> List[int]:
    current = 1
    result = []
    
    for _ in range(n):
      result.append(current)
      if current * 10 <= n:
        current *= 10
      else:
        if current >= n:
          current //= 10
        current += 1
        while current % 10 == 0:
          current //= 10
    
    return result

Explanation:

Since the problem states that we must use O(n) time, we cannot use the string-quicksort method.

Instead we resort to dfs. Lexicographic sorting means that we sort the numbers by their least significant digit. For example, 1,2,4,10,32 will be sorted into 1,10,2,32,4.

So to generate the lexicographic neighbours, we continuously multiply the current element by 10, effectively appending a digit and explore all the subsequent numbers before the least significant digit get affected.

When the least significant digit increments or we reach n, we divide back by 10 to reach back to our lowest possible state, and attempt to append-explore again.

To better visualise. Consider n = 13.

n = 13

we start with 1
Then the next lexicographic neighbour of 1 is 10, since 10 is less than 13 we can append this to our result.
Next, we explore neighbours of 10, which are 11, 12, 13, all of which are possible candidates.
Once we reach 13, we know that the next neighbour should be 2. We get there by dividing (integer divide) 13 by
10. So we get 1 back, then we can increment this to 2. 
The next neighbour of 2 should be 20, but since 20 > 13, we skip this and increment 2 instead to 3.
Continuing, we get 4,5,6,7,8,9.
Hence the final result = [1,10,11,12,13,2,3,4,5,6,7,8,9]

One thing to note, when dealing with edge cases like 19 -> 20, we need to mod 10 to get 20 back to 2. This 
ensures we are always exploring from the lowest possible state.

Hence in code:

def lexicalOrder(n):
  current = 1
  result = []
  
  for _ in range(n):
    result.append(current)
    if current <= n:
      current *= 10
    else:
      if current >= n:
        current //= 10
      current += 1
      while current % 10 == 0:
        current //= 10 
    
  return result

As mentioned, the time complexity is O(n) since we only need to do one pass from 1 to n.

The space complexity is O(1) if we do not count storing the result as extra space.

The full solution can be found near the top of the page.