# Lexicographical Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lexicographical-numbers)
Canonical: https://scaleengineer.com/dsa/problems/lexicographical-numbers
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Trie
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays)
---
## Problem
\[Fetch error\]

# Approaches
## Brute Force: Generate and Sort
This is the most straightforward and intuitive approach. It leverages the fact that the lexicographical order of numbers is equivalent to the alphabetical order of their string representations. The method involves generating all numbers, converting them to strings, sorting them, and then converting them back to integers.
**Time:** O(N * log(N) * log10(N)). The dominant operation is sorting. Sorting N items takes O(N log N) comparisons. Each comparison between two numbers (as strings) takes time proportional to the number of digits, which is O(log10(N)). · **Space:** O(N * log10(N)). We need to store N strings, and the average length of these strings is proportional to the number of digits in N, which is log10(N).
**Pros:** Simple to understand and implement.; Correctly solves the problem by using built-in functionalities.
**Cons:** Highly inefficient in terms of time complexity due to the expensive sorting step.; Requires significant extra space to store the string representations of all numbers.
### Explanation
The core idea is to transform the problem into a standard string sorting problem. 

First, we generate all integers from 1 to `n`. For each integer, we convert it into its string equivalent. These strings are stored in a list. For example, if `n=13`, we would create a list of strings: `["1", "2", "3", ..., "13"]`.

Next, we apply a standard lexicographical sort on this list of strings. After sorting, the list for `n=13` would become `["1", "10", "11", "12", "13", "2", "3", ..., "9"]`.

Finally, we iterate through this sorted list of strings, parse each string back into an integer, and add it to our final result list, which is then returned.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> lexicalOrder(int n) {
        // 1. Generate numbers and convert to strings
        List<String> stringList = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            stringList.add(String.valueOf(i));
        }

        // 2. Sort the list of strings lexicographically
        Collections.sort(stringList);

        // 3. Convert sorted strings back to integers
        List<Integer> result = new ArrayList<>();
        for (String s : stringList) {
            result.add(Integer.parseInt(s));
        }

        return result;
    }
}
```
### Algorithm
- Create a list to store the string representation of numbers from 1 to `n`.
- Iterate from 1 to `n`, convert each integer `i` to a string, and add it to the list.
- Use a standard sorting algorithm (like `Collections.sort()` in Java) to sort this list of strings lexicographically.
- Create a new list of integers.
- Populate the new list by parsing the sorted strings back into integers.
- Return the final list of integers.

## Recursive DFS Approach
A much more efficient approach is to view the numbers as being structured in a 10-ary tree (also known as a prefix tree or trie). The numbers can then be generated in lexicographical order by performing a pre-order traversal (Depth First Search) on this conceptual tree.
**Time:** O(N). Each number from 1 to `n` is visited and processed exactly once during the DFS traversal. · **Space:** O(log10(N)). This is for the recursion stack. The maximum depth of the recursion is the number of digits in `n`. This does not include the O(N) space for the output list.
**Pros:** Optimal time complexity of O(N).; The logic is elegant and directly models the hierarchical structure of lexicographical ordering.; Much more efficient than the brute-force approach.
**Cons:** Uses recursion, which can lead to a `StackOverflowError` for extremely large constraints, although this is unlikely given `n` is an `int`.; Slightly higher space overhead due to the recursion stack compared to a purely iterative solution.
### Explanation
In this model, the numbers 1 through 9 are the roots of nine distinct trees. The children of any node `curr` are `curr*10`, `curr*10 + 1`, ..., `curr*10 + 9`. A pre-order traversal naturally visits nodes in lexicographical order: parent, then children from left to right (e.g., 1, then 10, then 11...).

We implement this with a recursive `dfs` function. The main function initiates the DFS by calling it for each root, from 1 to 9. The `dfs` function first checks if the current number has exceeded `n`. If not, it adds the number to the result list and then recursively calls itself for all its valid children (those less than or equal to `n`). An important optimization is that once a child `curr*10 + j` exceeds `n`, we can stop checking subsequent siblings because they will also be greater than `n`.

```java
import java.util.ArrayList;
import java.util.List;

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

    private void dfs(int current, int n, List<Integer> result) {
        if (current > n) {
            return;
        }
        
        result.add(current);
        
        for (int i = 0; i <= 9; i++) {
            int next = current * 10 + i;
            if (next > n) {
                break; 
            }
            dfs(next, n, result);
        }
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Loop `i` from 1 to 9. For each `i`, call a helper function `dfs(i, n, result)`.
- The `dfs(current, n, result)` function is defined as:
  - If `current > n`, return (base case).
  - Add `current` to the `result` list (pre-order visit).
  - Loop `j` from 0 to 9 to form child numbers.
  - Calculate `next = current * 10 + j`.
  - If `next > n`, break the inner loop (pruning).
  - Recursively call `dfs(next, n, result)`.
- Return `result`.

## Iterative Approach
This approach achieves the same optimal time complexity as the DFS method but without using recursion. It iteratively calculates the next lexicographical number by simulating the pre-order traversal of the conceptual 10-ary tree. This makes it the most efficient solution in terms of both time and space.
**Time:** O(N). We generate each of the N numbers in the sequence. The logic to find the next number takes amortized constant time. · **Space:** O(1). We only use a few variables to keep track of the current number. This does not include the O(N) space required for the output list.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) (excluding the output list).; Avoids recursion, making it robust against stack overflow issues on platforms with limited stack depth.
**Cons:** The logic for finding the next number can be less intuitive and more complex to implement correctly compared to the recursive DFS approach.
### Explanation
We start with `current = 1` and add it to our result list. Then, in a loop that runs `n` times, we find the next number to add. The logic follows the pre-order traversal pattern:

1.  **Try to go deeper:** If `current * 10` is within the bound `n`, this is our next number. This is like moving to the first child in the tree (e.g., from 1 to 10).
2.  **Try to go to the next sibling:** If we can't go deeper, we try to increment `current`. This is possible if `current` doesn't end in 9 and `current + 1` is still within the bound `n`. This is like moving to a sibling node (e.g., from 12 to 13).
3.  **Backtrack and move to the next branch:** If neither of the above is possible (e.g., `current` is 19, or `current` is 13 when `n=13`), we have exhausted a subtree. We must backtrack by moving up the tree (`current /= 10`) until we find an ancestor that can be incremented to start a new branch. The next number is then this ancestor's next sibling (`(current / 10) + 1`).

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>(n);
        int current = 1;

        for (int i = 0; i < n; i++) {
            result.add(current);

            if ((long)current * 10 <= n) {
                current *= 10;
            } 
            else if (current % 10 != 9 && current + 1 <= n) {
                current++;
            } 
            else {
                while ((current / 10) % 10 == 9) {
                    current /= 10;
                }
                current = current / 10 + 1;
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` and an integer `current = 1`.
- Loop `n` times to generate `n` numbers.
- In each iteration, add `current` to `result`.
- Find the next `current` number using the following logic:
  - **Go Deeper:** If `current * 10 <= n`, update `current` to `current * 10`.
  - **Go to Sibling:** Else if `current % 10 != 9` and `current + 1 <= n`, update `current` to `current + 1`.
  - **Backtrack:** Otherwise, we have reached the end of a branch. Repeatedly divide `current` by 10 until its parent is not a '9' child (i.e., `(current / 10) % 10 != 9`). Then, update `current` to its parent's next sibling: `current = current / 10 + 1`.
- Return `result`.

# Solutions
### Java

```java
class Solution { public List < Integer > lexicalOrder ( int n ) { List < Integer > ans = new ArrayList <>(); int v = 1 ; for ( int i = 0 ; i < n ; ++ i ) { ans . add ( v ); if ( v * 10 <= n ) { v *= 10 ; } else { while ( v % 10 == 9 || v + 1 > n ) { v /= 10 ; } ++ v ; } } return ans ; } }
```

### JavaScript

```javascript
/** * @param {number} n * @return {number[]} */ var lexicalOrder = function ( n ) { let ans = []; function dfs ( u ) { if ( u > n ) { return ; } ans . push ( u ); for ( let i = 0 ; i < 10 ; ++ i ) { dfs ( u * 10 + i ); } } for ( let i = 1 ; i < 10 ; ++ i ) { dfs ( i ); } return ans ; };
```

### CPP

```cpp
class Solution { public: vector < int > lexicalOrder ( int n ) { vector < int > ans ; int v = 1 ; for ( int i = 0 ; i < n ; ++ i ) { ans . push_back ( v ); if ( v * 10 <= n ) v *= 10 ; else { while ( v % 10 == 9 || v + 1 > n ) v /= 10 ; ++ v ; } } return ans ; } };
```

### Python

```python
class Solution : def lexicalOrder ( self , n : int ) -> List [ int ]: v = 1 ans = [] for i in range ( n ): ans . append ( v ) if v * 10 <= n : v *= 10 else : while v % 10 == 9 or v + 1 > n : v //= 10 v += 1 return ans
```