Lexicographical Numbers In O(n) Time And O(1) Space
Lexicographical Numbers: Sort numbers from 1 to n in lexicographical order using DFS-like strategy. O(n) time complexity and O(1) extra space used.
386. Lexicographical Numbers Difficulty: Medium Topics: Depth-First Search, Trie Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order. You must write an algorithm that runs in O(n) time and uses O(1) extra space. 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: 4 Explanation: [1,2] Constraints: 1 <= n <= 5 * 104 Solution: We can approach it using a Depth-First Search (DFS)-like strategy. Key Insights: Lexicographical order is essentially a pre-order traversal over a virtual n-ary tree, whe...