386. Lexicographical Numbers – Leetcode Solutions

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]

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []  # List to store lexicographical order of numbers
        current = 1  # Start with the smallest lexicographical number
        
        for _ in range(n):
            result.append(current)  # Add the current number to the result list
            
            # Try to go deeper by appending a '0' (multiply by 10)
            if current * 10 <= n:
                current *= 10
            else:
                # Otherwise, increment to the next number
                if current >= n:
                    # While current ends with '9' or exceeds `n`, backtrack by removing the last digit
                    current //= 10
                current += 1
                # Remove trailing zeroes caused by overflow from n
                while current % 10 == 0:
                    current //= 10
                    
        return result

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        // Result vector to store lexicographical order
        vector<int> result;
        
        // Start the traversal from the number 1
        int current = 1;
        
        // We need exactly 'n' numbers in our result, so repeat 'n' times
        for (int i = 0; i < n; ++i) {
            result.push_back(current);
            
            // Try to go deeper (multiply current by 10) if possible
            if (current * 10 <= n) {
                current *= 10;
            } 
            else {
                // Otherwise, if we can't go deeper, increment the number
                // But we need to handle cases where this leads us out of bounds
                while (current % 10 == 9 || current + 1 > n) {
                    current /= 10; // Move up one level in lexicographical hierarchy
                }
                current++; // Move to the next number in the current level
            }
        }
        
        return result;
    }
};

var lexicalOrder = function(n) {
    // Initialize an empty array to store the lexicographical numbers
    let result = [];
    
    // Define a helper function that performs a depth-first traversal to generate numbers lexicographically
    function dfs(current) {
        // Base case: if the current number exceeds n, we stop the recursion
        if (current > n) return;
        
        // Add the current number to the result array
        result.push(current);
        
        // Try to build the next number by adding digits 0 to 9 to the end of `current`
        for (let i = 0; i < 10; i++) {
            let next = current * 10 + i;
            // If the generated number is greater than `n`, break out of the loop
            if (next > n) break;
            // Recursively call dfs with the newly generated number
            dfs(next);
        }
    }
    
    // Start with each number from 1 to 9, since we want lexicographical order
    for (let i = 1; i < 10; i++) {
        dfs(i);
    }
    
    // Return the result array containing all numbers in lexicographical order
    return result;
};

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        
        // Start the DFS from each number 1 to 9
        for (int i = 1; i <= 9; i++) {
            dfs(i, n, result);
        }
        
        return result;
    }

    // Helper function for depth-first search
    private void dfs(int current, int n, List<Integer> result) {
        // Base case: if the current number exceeds n, return
        if (current > n) {
            return;
        }
        
        // Add the current number to the result list
        result.add(current);
        
        // Explore the next numbers by appending digits 0 to 9
        for (int i = 0; i <= 9; i++) {
            // Generate the next number
            int next = current * 10 + i;
            // If the next number exceeds n, break
            if (next > n) {
                break;
            }
            // Recursively call dfs with the next number
            dfs(next, n, result);
        }
    }
}