321. Lexicographical Numbers
Given an integer n, return an array holding every integer from 1 to n, ordered lexicographically — the order their decimal spellings would appear in a dictionary. Under that order 10 comes before 2, because the string "10" precedes the string "2".
Sorting strings gets you there in O(n log n), but the real target is O(n) time with O(1) extra space (not counting the output): picture the numbers as one big 10-ary trie — the children of x are 10x through 10x + 9 — and emit its preorder traversal without ever materializing the tree.
Example 1:
Input: n = 13
Output: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: Everything spelled with a leading "1" comes first: 1, then its children 10–13 (14 through 19 exceed n). Only after the whole 1-branch is exhausted does 2 appear.
Example 2:
Input: n = 2
Output: [1, 2]
Explanation: With no two-digit numbers available, dictionary order and numeric order coincide.
Constraints:
- 1 ≤ n ≤ 5 * 10⁴
Hints:
Turning each number into its string and sorting works — the comparison "10" < "2" is exactly dictionary order. What does that cost, and what does it allocate?
Model the numbers as a trie rooted at 1–9 where the children of x are 10x … 10x + 9. Lexicographic order is this trie's preorder. To walk it iteratively from x: go deeper (x·10) if that stays ≤ n; otherwise step to x + 1 — but first climb up (x ÷ 10) while x ends in 9 or x + 1 would exceed n.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 13
Expected output: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]