algoadvance

Leetcode 386. Lexicographical Numbers

Problem Statement

Given an integer n, return 1 to n in lexicographical order.

Clarifying Questions

  1. Input Constraints:
    • What is the range of n?
      • Assume 1 <= n <= 50000.
  2. Output Format:
    • Should the output be a vector of integers?
      • Yes, the output should be a vector of integers arranged in lexicographical order.

Strategy

To solve this problem, we can use a depth-first search (DFS) approach. This method allows us to traverse the numbers in lexicographical order naturally.

Here’s the step-by-step strategy:

  1. Initialization: Create a result vector to store the lexicographical order numbers.
  2. DFS Function:
    • Create a helper function dfs that takes the current number and performs the depth-first search.
    • If the current number exceeds n, terminate that path.
    • Add the current number to the result vector.
    • For every number from 0 to 9, recursively call the dfs function with the current number extended by that digit if it forms a valid number within the range of n.
  3. Starting DFS:
    • Start the DFS traversal from numbers 1 to 9.

Code

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> result;
        for (int i = 1; i <= 9; i++) {
            dfs(i, n, result);
        }
        return result;
    }

private:
    void dfs(int current, int n, vector<int>& result) {
        if (current > n) return;
        result.push_back(current);
        for (int i = 0; i <= 9; i++) {
            if (current * 10 + i > n) return;
            dfs(current * 10 + i, n, result);
        }
    }
};

int main() {
    Solution solution;
    int n = 13;  // Example usage
    vector<int> result = solution.lexicalOrder(n);
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Time Complexity

The time complexity of this approach is O(n) because we visit each number from 1 to n exactly once.

Space Complexity

The space complexity is also O(n) due to the storage used for the result vector and the recursion stack during the DFS traversal.

By implementing this solution, you can efficiently generate the lexicographical numbers from 1 to n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI