386. Lexicographical Numbers

Description

Given an integer n, return all the numbers from 1 to n in lexicographical order.

Intuition

To generate numbers in lexicographical order, we can use a depth-first search (DFS) approach. By iteratively exploring numbers starting from each digit (1 through 9), we ensure that numbers are processed in a lexicographical sequence.

Approach

1. Initialization: Start by initializing an empty list to store the results.
2. Depth-First Search (DFS): - Begin the DFS with each number from 1 to 9. - For each number, generate its subsequent numbers by appending digits from 0 to 9. - Continue the DFS recursively until the generated number exceeds n.
3. Add Valid Numbers: Add each valid number to the result list during the DFS traversal.
4. Return Result: After completing the DFS for all starting digits, return the result list.

Complexity

Time Complexity:

O(n), where n is the input number. Each number from 1 to n is processed once.

Space Complexity:

O(n), for storing the result list and the recursion stack.

Code

C++

class Solution {
public:
    vector lexicalOrder(int n) {
        vector result;

        function dfs = [&](int baseIndex) {
            if (baseIndex * 10 > n) {
                return;
            }

            for (int i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; ++i) {
                result.push_back(i);
                dfs(i);
            }
        };

        for (int i = 1; i <= 9 && i <= n; ++i) {
            result.push_back(i);
            dfs(i);
        }

        return result;
    }
};

Python

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []

        def dfs(baseIndex):
            if baseIndex * 10 > n:
                return

            for i in range(baseIndex * 10, baseIndex * 10 + 10):
                if i > n:
                    break
                result.append(i)
                dfs(i)

        for i in range(1, 10):
            if i > n:
                break
            result.append(i)
            dfs(i)

        return result

Java

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

        dfs(result, n);

        return result;
    }

    private void dfs(List result, int n) {
        for (int i = 1; i <= 9 && i <= n; i++) {
            result.add(i);
            dfsHelper(result, i, n);
        }
    }

    private void dfsHelper(List result, int baseIndex, int n) {
        if (baseIndex * 10 > n) {
            return;
        }

        for (int i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++) {
            result.add(i);
            dfsHelper(result, i, n);
        }
    }
}

JavaScript

var lexicalOrder = function (n) {
    const arr = [];

    function dfs(baseIndex) {
        if (baseIndex * 10 > n) {
            return;
        }

        for (let i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++) {
            arr.push(i);
            dfs(i);
        }
    }

    let stack = [];

    for (let i = 1; i <= 9 && i <= n; i++) {
        arr.push(i);
        dfs(i);
    }

    return arr;
};