POTD: 440. K-th Smallest in Lexicographical Order

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:

1. Memory Overload: The solution generates all possible lexicographical numbers up to n and stores them in an array, which can be extremely large.
2. 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:

1. 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.

1. 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((log⁡n)×(log⁡n))=O((log⁡n)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.