📚Beginner-Friendly Guide to Solving "Lexicographical Numbers" LeetCode 1061

Are you struggling with LeetCode 386 Lexicographical Numbers? This comprehensive guide breaks down the optimal solution with detailed explanations, multiple programming language implementations, and expert insights to help you master this medium-difficulty algorithm problem.

📜What is LeetCode 386: Lexicographical Numbers Problem?

LeetCode 386 challenges developers to return all numbers from 1 to n sorted in lexicographical (dictionary) order, not numerical order. This problem tests your understanding of tree traversal algorithms, DFS simulation, and optimization techniques.

Problem Statement and Examples

Given an integer n, return all numbers from 1 to n sorted lexicographically.

Key Difference: Lexicographical vs Numerical Ordering

• Numerical Order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

• Lexicographical Order: 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9

Example Test Cases

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Explanation: Numbers sorted as strings in dictionary order

Example 2:

Input: n = 2
Output: [1,2]
Explanation: Both numbers maintain lexicographical order

Example 3:

Input: n = 100
Output: [1,10,100,11,12,13,14,...,19,2,20,21,...,29,3,30,...]

🧠Algorithm Strategy: DFS Tree Traversal Simulation

Why Not Sort Strings? Time Complexity Analysis

The naive approach of converting numbers to strings and sorting would result in:

• Time Complexity: O(n log n) - due to sorting operation

• Space Complexity: O(n) - for string conversion and storage

Our optimized solution achieves:

• Time Complexity: O(n) - each number processed exactly once

• Space Complexity: O(1) - constant extra space (excluding output array)

Core Algorithm Intuition

The lexicographical order follows a Depth-First Search (DFS) pattern without requiring recursion or additional data structures:

1. Depth Traversal: From any number, try going deeper by multiplying by 10 (1 → 10 → 100)

2. Sibling Traversal: If can't go deeper, increment by 1 (10 → 11 → 12)

3. Backtracking: When hitting boundaries (like 19 or n), backtrack by dividing by 10

Step-by-Step Algorithm Walkthrough

For n = 13, the traversal follows this pattern:

1. Start with curr = 1 → Add 1 to result

2. Try 1 * 10 = 10 ≤ 13 → Go deeper, curr = 10 → Add 10

3. Try 10 * 10 = 100 > 13 → Can't go deeper

4. Try 10 + 1 = 11 ≤ 13 → Move to sibling, curr = 11 → Add 11

5. Continue this pattern: 12, 13, then backtrack to 2, 3, 4, etc.

💻Complete Solution Implementation

C++ Solution (Most Efficient)

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> result;
        result.reserve(n); // Pre-allocate for better performance
        int curr = 1;
        
        while (result.size() < n) {
            result.push_back(curr);
            
            // Try to go deeper (multiply by 10)
            if (curr * 10 <= n) {
                curr *= 10;
            } else {
                // Backtrack until we can increment
                while (curr % 10 == 9 || curr == n) {
                    curr /= 10;
                }
                curr++;
            }
        }
        
        return result;
    }
};

JavaScript ES6+ Solution

/**
 * @param {number} n
 * @return {number[]}
 */
const lexicalOrder = function(n) {
    const result = [];
    let curr = 1;
    
    while (result.length < n) {
        result.push(curr);
        
        if (curr * 10 <= n) {
            curr *= 10;
        } else {
            while (curr % 10 === 9 || curr === n) {
                curr = Math.floor(curr / 10);
            }
            curr++;
        }
    }
    
    return result;
};

Python Solution with Type Hints

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        """
        Generate lexicographical order of numbers 1 to n
        Time: O(n), Space: O(1)
        """
        result = []
        curr = 1
        
        while len(result) < n:
            result.append(curr)
            
            if curr * 10 <= n:
                curr *= 10
            else:
                while curr % 10 == 9 or curr == n:
                    curr //= 10
                curr += 1
                
        return result

Java Solution

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>(n);
        int curr = 1;
        
        while (result.size() < n) {
            result.add(curr);
            
            if (curr * 10 <= n) {
                curr *= 10;
            } else {
                while (curr % 10 == 9 || curr == n) {
                    curr /= 10;
                }
                curr++;
            }
        }
        
        return result;
    }
}

Comprehensive Test Cases and Edge Cases

Standard Test Cases

// Test Case 1: Small range
Input: n = 9
Output: [1,2,3,4,5,6,7,8,9]
Explanation: No depth traversal needed

// Test Case 2: Powers of 10
Input: n = 100  
Output: [1,10,100,11,12,...,19,2,20,21,...,99]

// Test Case 3: Single digit
Input: n = 1
Output: [1]

Edge Cases to Consider

// Edge Case 1: Minimum valid input
n = 1 → [1]

// Edge Case 2: All single digits  
n = 9 → [1,2,3,4,5,6,7,8,9]

// Edge Case 3: Boundary at 10
n = 10 → [1,10,2,3,4,5,6,7,8,9]

// Edge Case 4: Large numbers
n = 50000 → Efficient O(n) performance maintained

Algorithm Complexity Analysis

Time Complexity Breakdown

• Overall: O(n) - Each number from 1 to n is visited exactly once

• Per iteration: O(1) - Constant time operations (multiplication, division, modulo)

• No sorting required: Unlike string-based approaches that need O(n log n)

Space Complexity Analysis

• Extra Space: O(1) - Only using a few integer variables

• Output Space: O(n) - Required for storing the result array

• No recursion stack: Iterative approach avoids stack overflow issues

Performance Comparison

Approach Time Complexity Space Complexity Pros Cons String Sort O(n log n) O(n) Simple to understand Inefficient for large n Recursive DFS O(n) O(log n) Intuitive tree traversal Stack overflow risk Iterative DFS O(n) O(1) Optimal performance Requires algorithm insight

Common Mistakes and Debugging Tips

Frequent Implementation Errors

Mistake 1: Incorrect Backtracking Logic

// Wrong: Not handling boundary cases properly
while (curr % 10 == 9) {  // Missing curr == n check
    curr /= 10;
}

Mistake 2: Integer Overflow

// Wrong: Not checking multiplication bounds
if (curr * 10 <= n) {  // Could overflow for large numbers
    curr *= 10;
}

// Better: Add overflow protection for very large n
if (curr <= n / 10) {
    curr *= 10;
}

Debugging Strategies

1. Trace Small Examples: Walk through n=13 step by step

2. Check Boundary Conditions: Test with n=1, n=9, n=10

3. Verify Order: Ensure output matches lexicographical expectations

4. Performance Testing: Validate O(n) complexity with large inputs

Interview Tips and Follow-up Questions

Technical Interview Insights

What interviewers look for:

• Understanding of lexicographical vs numerical ordering

• Ability to optimize from O(n log n) to O(n) solution

• Clean implementation without recursion

• Proper handling of edge cases

Potential Follow-up Questions

Question 1: Memory Optimization

"Can you solve this without storing all results at once?"

Answer: Implement as a generator/iterator that yields one number at a time:

def lexical_order_generator(n):
    curr = 1
    count = 0
    
    while count < n:
        yield curr
        count += 1
        
        if curr * 10 <= n:
            curr *= 10
        else:
            while curr % 10 == 9 or curr == n:
                curr //= 10
            curr += 1

Question 2: Range Queries

"How would you find lexicographical numbers between two values?"

Question 3: k-th Lexicographical Number

"Can you find the k-th lexicographical number without generating all previous numbers?"

Related LeetCode Problems

Master these similar problems to strengthen your algorithm skills:

• LeetCode 440: K-th Smallest in Lexicographical Order

• LeetCode 17: Letter Combinations of a Phone Number

• LeetCode 89: Gray Code

• LeetCode 131: Palindrome Partitioning

Conclusion

LeetCode 386 demonstrates the power of simulating tree traversal without recursion, achieving optimal O(n) time complexity through clever iteration logic. This problem showcases important concepts:

• Algorithm optimization from O(n log n) to O(n)

• Space-efficient implementation using O(1) extra memory

• DFS simulation without recursion or additional data structures

• Boundary handling and edge case management

The key insight is recognizing that lexicographical order follows a predictable DFS pattern that can be efficiently simulated using simple arithmetic operations.

Next Steps for Skill Development

1. Practice variations with different constraints

2. Implement in multiple languages to understand language-specific optimizations

3. Study related tree traversal problems to reinforce the pattern

4. Time your solutions to verify O(n) performance in practice

Ready to tackle more challenging algorithm problems? The skills learned from LeetCode 386 will serve as a strong foundation for advanced tree traversal and optimization techniques.

If you enjoyed the breakdown, consider hitting that ❤️ and sharing with fellow devs. Let’s keep growing and solving, one problem at a time! 🔍💻

Happy coding! 🚀