🎨Now live: Try our Free AI Image Generation Feature

Description
Given an integer n
, return all the numbers from 1 to n
in lexicographical order.
Intuition
To generate numbers in lexicographical order, we can use a depth-first search (DFS) approach. By iteratively exploring numbers starting from each digit (1 through 9), we ensure that numbers are processed in a lexicographical sequence.
Approach
- Initialization: Start by initializing an empty list to store the results.
- Depth-First Search (DFS):
- Begin the DFS with each number from 1 to 9.
- For each number, generate its subsequent numbers by appending digits from 0 to 9.
- Continue the DFS recursively until the generated number exceeds
n
. - Add Valid Numbers: Add each valid number to the result list during the DFS traversal.
- Return Result: After completing the DFS for all starting digits, return the result list.
Complexity
Time Complexity:
O(n), where n
is the input number. Each number from 1 to n
is processed once.
Space Complexity:
O(n), for storing the result list and the recursion stack.
Code
C++
class Solution {
public:
vector lexicalOrder(int n) {
vector result;
function dfs = [&](int baseIndex) {
if (baseIndex * 10 > n) {
return;
}
for (int i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; ++i) {
result.push_back(i);
dfs(i);
}
};
for (int i = 1; i <= 9 && i <= n; ++i) {
result.push_back(i);
dfs(i);
}
return result;
}
};
Python
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
result = []
def dfs(baseIndex):
if baseIndex * 10 > n:
return
for i in range(baseIndex * 10, baseIndex * 10 + 10):
if i > n:
break
result.append(i)
dfs(i)
for i in range(1, 10):
if i > n:
break
result.append(i)
dfs(i)
return result
Java
class Solution {
public List lexicalOrder(int n) {
List result = new ArrayList<>();
dfs(result, n);
return result;
}
private void dfs(List result, int n) {
for (int i = 1; i <= 9 && i <= n; i++) {
result.add(i);
dfsHelper(result, i, n);
}
}
private void dfsHelper(List result, int baseIndex, int n) {
if (baseIndex * 10 > n) {
return;
}
for (int i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++) {
result.add(i);
dfsHelper(result, i, n);
}
}
}
JavaScript
var lexicalOrder = function (n) {
const arr = [];
function dfs(baseIndex) {
if (baseIndex * 10 > n) {
return;
}
for (let i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++) {
arr.push(i);
dfs(i);
}
}
let stack = [];
for (let i = 1; i <= 9 && i <= n; i++) {
arr.push(i);
dfs(i);
}
return arr;
};