Sponsored
Sponsored
The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.
Time Complexity: O(n), Space Complexity: O(1) (excluding the output array).
1const dfs = (current, n, result) => {
2 if (current > n) return;
3 result.push(current);
4 for (let i = 0; i <= 9; i++) {
5 if (current * 10 + i > n) return;
6 dfs(current * 10 + i, n, result);
7 }
8};
9
10const lexicalOrder = (n) => {
11 const result = [];
12 for (let i = 1; i < 10; i++) {
13 dfs(i, n, result);
14 }
15 return result;
16};
17
18const n = 13;
19console.log(lexicalOrder(n));This JavaScript code employs recursion and an array to append numbers in lexicographical order by invoking dfs iteratively, emulating a lexicographical tree traversal.
This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.
Time Complexity: O(n), Space Complexity: O(1) (ignoring return array).
1using System.Collections.Generic;
public class IterativeLexicalOrder {
public IList<int> LexicalOrder(int n) {
IList<int> result = new List<int>();
int num = 1;
for (int i = 0; i < n; ++i) {
result.Add(num);
if (num * 10 <= n) {
num *= 10;
} else {
while (num % 10 == 9 || num + 1 > n) {
num /= 10;
}
num++;
}
}
return result;
}
public static void Main(string[] args) {
IterativeLexicalOrder obj = new IterativeLexicalOrder();
int n = 13;
IList<int> result = obj.LexicalOrder(n);
foreach (int num in result) {
Console.Write(num + " ");
}
}
}This C# solution efficiently and iteratively computes the lexicographical order by leveraging systematic incrementation and resetting techniques to generate valid sequential numbers.