Lexicographical Numbers
Medium · Tries · Explanation and code example
Iterative Decimal-Prefix Traversal
How it works
Lexicographic order follows a decimal prefix tree. Descend by multiplying the current value by ten when that child exists. Otherwise remove exhausted trailing digits and move to the next sibling, visiting each integer without sorting strings.
Steps
- Start at one and append the current value.
- Descend to current × 10 when it is <= n.
- Otherwise climb past trailing nines or the upper boundary and increment.
Complexity
- Time: O(n) amortized.
- Space: O(n) output and O(1) extra workspace.
Things to watch for
- Numeric sorting does not match lexicographic order.
- Climbing can remove several trailing digits.
- Emit exactly n values.
Python code example
class Solution:
def lexicalOrder(self, n: int) -> list[int]:
ans = []
curr = 1
while len(ans) < n:
ans.append(curr)
if curr * 10 <= n:
curr *= 10
else:
while curr % 10 == 9 or curr == n:
curr //= 10
curr += 1
return ans
C++ code example
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;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.