• Posts

Problem 440 K-th Smallest in Lexicographical Order

Problem Statement

Link - Problem 440

Question

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

Solution

class Solution {
public:
    int findKthNumber(int n, int k) {
        int curr = 1;
        k--;

        while (k > 0) {
            int step = countSteps(n, curr, curr + 1);
            if (step <= k) {
                curr++;
                k -= step;
            } else {
                curr *= 10;
                k--;
            }
        }

        return curr;
    }

private:
    int countSteps(int n, long prefix1, long prefix2) {
        int steps = 0;
        while (prefix1 <= n) {
            steps += min((long)(n + 1), prefix2) - prefix1;
            prefix1 *= 10;
            prefix2 *= 10;
        }
        return steps;
    }
};

Complexity Analysis

| Algorithm                              | Time Complexity  | Space Complexity |
| -------------------------------------- | ---------------- | ---------------- |
| Incremental Lexicographical Generation | O(log(n) log(k)) | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we need to consider the lexicographical order of the numbers in the given range. This involves comparing numbers based on their string representations rather than their actual numerical values. Initially, we should think about how the order changes as we move from one number to the next, and identify any patterns or regularities. We should also consider how the range of numbers affects the order. Key points to consider are: understanding lexicographical order, recognizing patterns in the order, identifying key milestones like powers of 10, and considering the impact of the range on the order.

Intuitive Analysis

The key to solving this problem intuitively lies in understanding how numbers are arranged in lexicographical order and recognizing the pattern that emerges when counting through the numbers. Intuitive analysis involves realizing that as we move from one number to the next, the order can change significantly at certain points, such as when moving from single-digit to two-digit numbers. We should think about how many steps it takes to move through a certain range of numbers in lexicographical order, such as the difference between consecutive numbers and how this changes as numbers get larger. Key points for intuitive analysis include: stepping through the numbers in lexicographical order, recognizing how the number of steps changes as numbers increase, understanding the role of powers of 10 as dividers between large groups of numbers, and considering how to navigate through the numbers efficiently to find the kth number.

1. Intuition

• The problem requires finding the kth lexicographically smallest integer in the range [1, n], which means we need to consider the numbers in a dictionary order
• To solve this problem, we can use a prefix-based approach, where we start with the smallest possible prefix (1) and then extend it by appending digits
• The key insight is to calculate the number of steps required to move from one prefix to the next, which can be done using the countSteps function
• This function calculates the number of integers in the range [prefix1, prefix2) that are less than or equal to n
• By iteratively calculating the steps and updating the current prefix, we can find the kth lexicographically smallest integer
• The time complexity of this approach is O(log n + log k) because we are essentially performing a binary search in the lexicographical order
• The space complexity is O(1) because we only use a constant amount of space to store the current prefix and the number of steps

2. Implementation

• The findKthNumber function initializes the current prefix to 1 and decrements k by 1 to make it 0-indexed
• The while loop continues until k becomes 0, at which point the current prefix is the kth lexicographically smallest integer
• Inside the loop, we calculate the number of steps required to move from the current prefix to the next prefix using the countSteps function
• If the number of steps is less than or equal to k, we increment the current prefix and subtract the steps from k
• Otherwise, we multiply the current prefix by 10 to move to the next level of prefixes and decrement k by 1
• The countSteps function calculates the number of integers in the range [prefix1, prefix2) that are less than or equal to n using a while loop
• The loop continues until prefix1 exceeds n, at which point we return the total number of steps

Complexity Analysis

Time Complexity:

• The algorithm’s time complexity is driven by the while (k > 0) loop in the findKthNumber function, which iterates until k becomes 0. In each iteration, the countSteps function is called to calculate the number of steps required to move from curr to curr + 1. The time complexity of countSteps is O(log(n)) because it involves a while loop that runs until prefix1 exceeds n, with prefix1 being multiplied by 10 in each iteration. Therefore, the overall time complexity of the algorithm is O(log(n) log(k)) due to the nested loops.
• The dominant operation in the algorithm is the countSteps function, which is called repeatedly in the while (k > 0) loop. The countSteps function has a time complexity of O(log(n)) due to the while loop, and this complexity is compounded by the outer loop, resulting in a time complexity of O(log(n) log(k)).
• The Big O classification of O(log(n) log(k)) is justified because the algorithm’s time complexity grows logarithmically with both n and k. The logarithmic growth is due to the use of multiplication by 10 in the countSteps function, which reduces the number of iterations required to exceed n. The nested loops and the logarithmic growth of the countSteps function contribute to the overall time complexity of O(log(n) log(k)).

Space Complexity:

• The algorithm has a space complexity of O(1) because it only uses a constant amount of space to store the variables n, k, curr, and step. The countSteps function also uses a constant amount of space to store the variables steps, prefix1, and prefix2. The space usage does not grow with the input size n or k, resulting in a space complexity of O(1).
• The data structures used in the algorithm, such as integers and long integers, have a fixed size and do not contribute to the space complexity. The algorithm does not use any dynamic data structures, such as arrays or linked lists, that could grow with the input size and affect the space complexity.
• The space complexity of O(1) is justified because the algorithm’s memory usage is constant and does not depend on the input size n or k. The use of a fixed amount of space to store variables and the lack of dynamic data structures contribute to the overall space complexity of O(1).

Footnote

This question is rated as Hard difficulty.

Similar Questions: