440. K-th Smallest in Lexicographical Order

[mah-shamim]

Topics: Trie

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Example 1:

• Input: n = 13, k = 2
• Output: 10
• Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2:

• Input: n = 1, k = 1
• Output: 1

Constraints:

• 1 <= k <= n <= 109

[basharul-siddike]

The idea is to traverse through numbers as they would appear in a lexicographical order, similar to performing a depth-first search (DFS) on a Trie.

Approach:

1. We can visualize this as a Trie where each node represents a number, and the children of a node x are 10 * x + 0, 10 * x + 1, ..., 10 * x + 9.
2. Starting from 1, we explore numbers in lexicographical order, counting how many numbers can be placed before we reach the kth one.
3. The key part of the solution is to efficiently compute the number of integers between start and end in a lexicographical order. This will help us skip some branches when needed.

Steps:

1. Start from the root number 1.
2. Use a helper function to calculate how many numbers exist between prefix and the next prefix (prefix+1).
3. Based on this count, decide whether to move deeper in the current prefix (by multiplying it by 10) or move to the next sibling prefix (by incrementing the current prefix).

Let's implement this solution in PHP: 440. K-th Smallest in Lexicographical Order

<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @return Integer
 */
function findKthNumber($n, $k) {
    $current = 1; // Start with '1'
    $k--; // Decrement k because we are starting with the first element

    while ($k > 0) {
        $steps = calculateSteps($n, $current, $current + 1);

        if ($steps <= $k) {
            // If the k-th number is not in this prefix, move to the next prefix
            $current++;
            $k -= $steps; // Decrease k by the number of steps skipped
        } else {
            // If the k-th number is in this prefix, move deeper in this branch
            $current *= 10;
            $k--; // We are considering the current number itself
        }
    }

    return $current;
}

/**
 * Helper function to calculate the number of steps between two prefixes in the range [1, n]
 *
 * @param $n
 * @param $prefix1
 * @param $prefix2
 * @return int|mixed
 */
function calculateSteps($n, $prefix1, $prefix2) {
    $steps = 0;

    while ($prefix1 <= $n) {
        $steps += min($n + 1, $prefix2) - $prefix1;
        $prefix1 *= 10;
        $prefix2 *= 10;
    }

    return $steps;
}

// Test cases
echo findKthNumber(13, 2); // Output: 10
echo "\n";
echo findKthNumber(1, 1); // Output: 1
?>

Explanation:

1. findKthNumber function:

   • We start at the root (current = 1).
   • We decrement k by 1 because the first number is already considered (i.e., we start with 1).
   • We then use the calculateSteps function to determine how many numbers lie between current and current + 1 in lexicographical order.
   • If the number of steps is less than or equal to k, it means the k-th number is not within the current prefix, so we move to the next prefix (current++).
   • If the k-th number is within the current prefix, we go deeper into the tree (current *= 10).
   • We continue this process until k becomes 0.

2. calculateSteps function:

   • This function calculates how many numbers there are in lexicographical order between prefix1 and prefix2 within the range of n.
   • It uses a while loop to compute the steps at each level of the "tree" (i.e., between numbers with the same prefix but different lengths).

Time Complexity:

The time complexity is approximately O(log n), where n is the input range. This is because in each step, we either go deeper into the current prefix or move to the next prefix, and both operations are logarithmic relative to n.

This solution is efficient even for large inputs where n can be as large as 10^9.

[mah-shamim]

Thanks to solve the "K-th Smallest in Lexicographical Order" problem

[basharul-siddike]

Thanks