LeetCode 386: Lexicographical Numbers Solution
Master LeetCode problem 386 (Lexicographical Numbers), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
386. Lexicographical Numbers
Problem Explanation
Explanation
To solve this problem, we can leverage the lexicographical ordering of numbers. We can achieve the desired ordering by simulating a depth-first search (DFS) traversal of a tree where each node represents a number. The idea is to explore the numbers in lexicographical order by repeatedly multiplying the current number by 10 and adding numbers from 0 to 9. We start from 1 and keep appending numbers until we reach n.
The key observations are:
- When we move from a number x to x10, the numbers in between are x10, x10+1, x10+2, ..., x*10+9.
- If x10 <= n, we can explore the subtree rooted at x10. If not, we need to backtrack to the parent node and increment it to x+1.
By following the above observations, we can generate the lexicographically sorted numbers from 1 to n efficiently.
Time Complexity: The time complexity of this solution is O(n) because we are exploring each number once.
Space Complexity: The space complexity is O(1) as we are not using any additional space proportional to n.
Solution Code
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
int current = 1;
for (int i = 1; i <= n; i++) {
res.add(current);
if (current * 10 <= n) {
current *= 10;
} else {
if (current >= n) current /= 10;
current += 1;
while (current % 10 == 0) current /= 10;
}
}
return res;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 386 (Lexicographical Numbers)?
This page provides optimized solutions for LeetCode problem 386 (Lexicographical Numbers) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 386 (Lexicographical Numbers)?
The time complexity for LeetCode 386 (Lexicographical Numbers) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 386 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 386 in Java, C++, or Python.