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

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]

Solution

Method 1 - DFS

Using DFS in a preorder manner(i.e. add the result as soon as we find it and then process the children) to generate numbers in lexicographical order:

  1. Start from the number 1.
  2. Recursively try to go deeper (multiplying by 10) to maintain the smallest lexical order.
  3. If multiplying is not possible, i.e. number exceed n, we backtrack , and consider the next number (increment), and go to siblings
  4. Continue this process until all numbers are processed.

For eg.. number 133, here is how the dfs tree:

 graph TD
     A["Start"]
     A --> B1["1"]
     A --> B2["2"]
     A --> B3["3"]
     A --> B4["..."]
     B1 --> C1["10"]
     B1 --> C2["11"]
     B1 --> C3["12"]
     B1 --> C4["13"]
     B1 --> C5["..."]
     B1 --> C6["19"]
     C1 --> D1["100"]
     C1 --> D2["101"]
     C1 --> D3["..."]
     C1 --> D4["109"]
     D1 ---> E1["1000"]
     C2 --> F1["110"]
     C2 --> F2["111"]
     C2 --> F3["..."]
     C2 --> F4["119"]
     C3 --> G1["120"]
     C3 --> G2["..."]
     C4 --> G3["130"]
     C4 --> G4["131"]
     C4 --> G5["132"]
     C4 --> G6["133"]

E1:::red
classDef red fill:#f96,stroke:#333,stroke-width:2px;

Code

Java
public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            dfs(i, n, ans);
        }
        return result;
    }

    private void dfs(int current, int n, List<Integer> ans) {
        if (current > n) {
            return;
        }
        ans.add(current);
        for (int i = 0; i < 10; i++) {
            if (10 * current + i > n) {
                return;
            }
            dfs(10 * current + i, n, ans);
        }
    }
}
Python
class Solution:
    def lexicalOrder(self, n: int):
        result = []
        for i in range(1, 10):
            self.dfs(i, n, result)
        return result

    def dfs(self, current, n, result):
        if current > n:
            return
        result.append(current)
        for i in range(10):
            next_num = 10 * current + i
            if next_num > n:
                return
            self.dfs(next_num, n, result)

Complexity

  • ⏰ Time complexity: O(n), because we generate and process each number exactly once.
  • 🧺 Space complexity: O(1)
    • Typical recursion depth in the worst case can be (O(\log_{10} n)), but this is not considered extra space complexity based on the problem constraints.

Method 2 - Iterative

To generate numbers in lexicographical order from 1 to n, we simulate the process of numbering in dictionary order by:

  1. Initializing the current number as 1.
  2. Attempting to multiply the current number by 10 if possible to maintain the smallest lexical order.
  3. Incrementing the number when multiplying results in a value greater than n.
  4. Handling cases where the incremented number results need adjusting to valid lexicographical numbers.

Code

Java
public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        int current = 1;
        for (int i = 0; i < n; i++) {
            ans.add(current);
            if (current * 10 <= n) {
                current *= 10;
            } else {
                if (current >= n) {
                    current /= 10;
                }
                current++;
                while (current % 10 == 0) {
                    current /= 10;
                }
            }
        }
        return result;
    }
}
Python
class Solution:
    def lexicalOrder(self, n: int):
        result = []
        current = 1
        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

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)