Lexicographical Numbers — Solution in Python, Java & C++
Lexicographical Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Lexicographical Numbers is a medium coding problem on depth-first search and trie, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trie
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return every integer from 1 to n (inclusive) arranged in lexicographical order — the order a dictionary would list them if each number were written out as a string of digits.
So 10 comes before 2 (the string "10" starts with "1"), and 1 comes before 10 (a prefix sorts first).
Your algorithm should run in O(n) time and use O(1) extra space beyond the output.
Example 1
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Explanation: Every number that starts with the digit 1 comes before 2.
Example 2
Input: n = 2
Output: [1,2]
Example 3
Input: n = 1
Output: [1]
Constraints
1 <= n <= 5 * 10^4
Hints for Lexicographical Numbers
Hint 1
Picture the numbers as a tree: the children of
xare10x, 10x + 1, …, 10x + 9. Lexicographic order is a pre-order walk of that tree.Hint 2
You don't need recursion or a stack — from the current number you can compute the next one directly.
Hint 3
Go down (
x * 10) when that is still<= n. Otherwise step to the next siblingx + 1, but first climb up (x / 10) whilexends in9orx + 1 > n.
How to solve Lexicographical Numbers
Lexicographic order on decimal strings is exactly a pre-order traversal of the 10-ary tree whose root's children are 1…9 and where x has children 10x … 10x + 9. The successor of any node in that walk can be computed in amortised constant time, so the whole list is produced without sorting.
Approach
- Start with
cur = 1and repeatntimes: appendcurto the answer. - If
cur * 10 <= n, the next number is its first childcur * 10. - Otherwise, while
curends in9orcur + 1 > n, climb to the parentcur / 10(integer division). - Then move to the next sibling:
cur += 1.
Why it works
In a pre-order walk the node after x is its first child if it has one; if not, it is the next sibling of the nearest ancestor (including x itself) that still has a next sibling inside 1…n. A node ending in 9 is a last child, and x + 1 > n means the sibling is out of range — in both cases we climb. Each climb undoes an earlier descent, so the total work is O(n).
Complexity
- Time —
O(n) - Space —
O(1) besides the output
Pitfalls
- Sorting the numbers as strings works but costs
O(n log n)and allocates a string per number. - Climbing must also happen when
cur + 1 > n, not only whencurends in9— e.g. after13withn = 13the next number is2. cur * 10stays far below 2^31 becausecur <= n <= 5 * 10^4.
Reference solution
Python
from typing import List
def lexicalOrder(n: int) -> List[int]:
out = []
cur = 1
for _ in range(n):
out.append(cur)
if cur * 10 <= n:
cur *= 10
else:
while cur % 10 == 9 or cur + 1 > n:
cur //= 10
cur += 1
return outJava
public static int[] lexicalOrder(int n) {
int[] out = new int[n];
int cur = 1;
for (int i = 0; i < n; i++) {
out[i] = cur;
if (cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 == 9 || cur + 1 > n) cur /= 10;
cur += 1;
}
}
return out;
}C++
vector<int> lexicalOrder(int n) {
vector<int> out;
out.reserve(n);
int cur = 1;
for (int i = 0; i < n; i++) {
out.push_back(cur);
if (cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 == 9 || cur + 1 > n) cur /= 10;
cur += 1;
}
}
return out;
}JavaScript
var lexicalOrder = function(n) {
var out = [];
var cur = 1;
for (var i = 0; i < n; i++) {
out.push(cur);
if (cur * 10 <= n) {
cur *= 10;
} else {
while (cur % 10 === 9 || cur + 1 > n) cur = Math.floor(cur / 10);
cur += 1;
}
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Trie (Prefix Tree)