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

Video Explanation

Video explanation

Here is the video explaining this method in detail. Please check it out:

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["..."]
     A --> B4["9"]
     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> ans = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            dfs(i, n, ans);
        }
        return ans;
    }

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

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

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 curr 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 curr = 1;
        for (int i = 0; i < n; i++) {
            ans.add(curr);
            if (curr * 10 <= n) {
                curr *= 10;
            } else {
                if (curr >= n) {
                    curr /= 10;
                }
                curr++;
                while (curr % 10 == 0) {
                    curr /= 10;
                }
            }
        }
        return ans;
    }
}
Python
class Solution:
    def lexicalOrder(self, n: int):
        ans = []
        curr = 1
        for _ in range(n):
            ans.append(curr)
            if curr * 10 <= n:
                curr *= 10
            else:
                if curr >= n:
                    curr //= 10
                curr += 1
                while curr % 10 == 0:
                    curr //= 10
        return ans

Complexity

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