If you will use the DFS you will get the runtime error is due to memory issues when trying to use a depth-first search (DFS) strategy to generate all numbers lexicographically up to `n`

and store them in an array (`result`

). This approach is inefficient for large inputs because it consumes a lot of memory, leading to heap out-of-memory errors.

### Key Issues:

**Memory Overload**: The solution generates all possible lexicographical numbers up to`n`

and stores them in an array, which can be extremely large.**Time Complexity**: Generating all lexicographical numbers is inefficient, and you only need the k-th number, not all the numbers.

### Optimization:

Instead of generating all numbers and storing them, you can directly calculate the steps between numbers and simulate the traversal without storing unnecessary data. The key is to count the lexicographical steps between numbers and intelligently skip subtrees of numbers that don’t need to be explored.

### Improved Approach:

We can modify the solution to avoid creating a massive array by following the optimized version of DFS traversal without storing numbers.

Here’s an optimized version of your code using the previously discussed strategy, which efficiently finds the k-th smallest number without storing all the numbers:

```
var findKthNumber = function(n, k) {
let curr = 1; // Start from 1
k--; // Convert k to 0-based index
// Helper function to count steps between curr and n
function countSteps(curr, n) {
let steps = 0;
let first = curr;
let last = curr;
// Count all numbers between `first` and `last` at each level
while (first <= n) {
steps += Math.min(n + 1, last + 1) - first;
first *= 10;
last = last * 10 + 9;
}
return steps;
}
// Find the k-th lexicographical number
while (k > 0) {
const steps = countSteps(curr, n);
if (steps <= k) {
// Skip this subtree, move to next number
curr += 1;
k -= steps;
} else {
// Go deeper into the subtree
curr *= 10;
k -= 1;
}
}
return curr;
};
// Example usage
const n = 13, k = 2;
console.log(findKthNumber(n, k)); // Output: 10
```

### Explanation of the Optimized Approach:

:`countSteps(curr, n)`

- This function calculates how many numbers exist lexicographically between the number
`curr`

and`n`

. - It explores how many numbers exist under the subtree rooted at
`curr`

and compares it with`n`

.

**Main loop**:

- We start from
`curr = 1`

and try to find the`k`

-th lexicographical number. - If the number of steps from
`curr`

to the next potential number is less than or equal to`k`

, we skip this entire range by increasing`curr`

. - If the steps are greater than
`k`

, we go deeper (by multiplying`curr`

by 10, moving to the next lexicographical level). - We repeat this until we have reduced
`k`

to zero, indicating we have found the`k`

-th number.

### Why this works:

**Memory-efficient**: We avoid storing all lexicographical numbers and instead simulate the process by counting steps.**Efficient traversal**: We skip unnecessary parts of the lexicographical tree if they don’t contain the k-th number.

### Overall Time Complexity:

The number of iterations in the main loop is proportional to `log n`

, and within each iteration, the `countSteps`

function also takes `O(log n)`

time. Thus, the total time complexity is:

O((logn)×(logn))=O((logn)2)O((\log n) \times (\log n)) = O((\log n)^2)O((logn)×(logn))=O((logn)2)

### Explanation:

- The
`countSteps`

function takes`O(log n)`

time because it calculates the number of steps between`curr`

and`n`

by checking numbers at each level of the lexicographical tree. - The main loop iterates
`O(log n)`

times, as`curr`

is either incremented or moved deeper into the tree by a factor of 10.

Thus, the overall time complexity is ** O((log n)^2)**.

This is much more efficient than generating all numbers, which would take `O(n)`

time, especially when `n`

is large.

This approach should fix the memory error and efficiently solve the problem within the constraints.