Hey tech trailblazers! 🚀
Today, we’re exploring a deceptively simple but algorithmically clever problem — LeetCode 386: Lexicographical Numbers. This one’s all about simulating dictionary-like traversal of numbers from 1 to n, and we’ll solve it in O(n) time without recursion or heavy data structures. Let’s dive in! 💡

📜 Problem Overview

You’re given an integer n.
Your goal is to return all numbers from 1 to n sorted lexicographically, not numerically.

📘 Lexicographical Order = Dictionary order
For example:

Numerical:     1, 2, 3, 4, ..., 10, 11
Lexicographical: 1, 10, 11, 2, 3, ..., 9

📝 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]

🧠 Intuition & Strategy

If we sort the numbers as strings, it’s easy — but that costs O(n log n) and uses extra space. ❌

The challenge here is to do this in:

• ⏱ O(n) time
• 💾 O(1) extra space (excluding the output array)

✅ Observation:

The lexicographical order of numbers can be traversed like a DFS tree, where:

• Going deeper = appending 0 (multiply by 10)
• Moving sideways = incrementing by 1 (unless we hit a boundary like 9 or n)

💡 Greedy DFS Simulation

Start from 1, and simulate:

1. If curr * 10 <= n → go to the next depth (i.e., 1 → 10, 2 → 20, etc.)
2. Else, if curr % 10 != 9 and curr + 1 <= n → move to the next sibling
3. If we can't move forward (e.g., from 19, curr = 20 is > n) → backtrack using curr /= 10 until we can increment again

This mimics DFS without recursion or a stack.

⚙️ C++ Code (Optimized)

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        int curr = 1;

        while (ans.size() < n) {
            ans.push_back(curr);
            if (curr * 10 <= n) {
                curr *= 10;
            } else {
                while (curr % 10 == 9 || curr == n)
                    curr /= 10;
                ++curr;
            }
        }

        return ans;
    }
};

🌐 JavaScript Version

var lexicalOrder = function(n) {
    const ans = [];
    let curr = 1;

    while (ans.length < n) {
        ans.push(curr);
        if (curr * 10 <= n) {
            curr *= 10;
        } else {
            while (curr % 10 === 9 || curr === n) {
                curr = Math.floor(curr / 10);
            }
            curr++;
        }
    }

    return ans;
};

🐍 Python Version

class Solution:
    def lexicalOrder(self, n: int) -> list[int]:
        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

🧪 Test Case Scenarios

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Input: n = 2
Output: [1,2]

Input: n = 1
Output: [1]

Input: n = 100
Output: [1,10,100,11,12,13,14,...,2,20,...,99]

Input: n = 9
Output: [1,2,3,4,5,6,7,8,9]  // No depth traversal, just linear

🧮 Time & Space Complexity

Time Complexity: O(n)  
- Each number is processed exactly once

Space Complexity: O(1)
- No extra data structures used (besides output)

✅ This solution fully respects the space and time constraints set by the problem — making it both elegant and interview-worthy.

✨ Wrap Up

This problem is a brilliant example of how string logic and DFS intuition can be implemented in a space-efficient way.

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! 🚀