Jobs

Interviews

Discussions

K-th Smallest in Lexicographical Order

Hard

Samsung

1 view

Topics:

TreesGreedy Algorithms

Given two integers n and k, return the k^th 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 <= 10⁹

K-th Smallest in Lexicographical Order

Hard

Samsung

1 view

Topics:

TreesGreedy Algorithms

Given two integers n and k, return the k^th 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 <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` (the upper bound for the numbers) and `k` (the desired lexicographical rank)? What are the maximum possible values for these inputs?
Is `k` guaranteed to be a valid rank, meaning that it will always be within the range of possible numbers formed from 1 to `n`?
What should I return if `k` is greater than the number of integers that can be formed lexicographically from 1 to `n`?
By 'lexicographical order', do you mean string-based lexicographical order (e.g., '10' comes before '2')?
Are `n` and `k` always positive integers?

Brute Force Solution

Approach

The brute force method for finding the K-th smallest number lexicographically involves generating every number within a certain range as strings. We then sort these strings alphabetically, and the K-th entry in this sorted list is our answer. This is like making a complete dictionary of all possible numbers and finding the one at the K-th page.

Here's how the algorithm would work step-by-step:

First, create a list of all numbers from 1 up to the given maximum number.
Think of these numbers as words in a dictionary.
Next, arrange these numbers in the way a dictionary would: alphabetically.
Finally, find the number that is in the K-th position in this sorted dictionary. That number is the answer.

Code Implementation

def find_kth_smallest_lexicographical(maximum_number, k_value):
    # Create a list of all numbers from 1 to maximum_number.
    number_list = [str(number) for number in range(1, maximum_number + 1)]

    # Sort the numbers lexicographically (as strings).
    number_list.sort()

    # Return the k_value-th element in the sorted list.
    # Adjust index because lists are zero-indexed.
    return int(number_list[k_value - 1])

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first generates a list of n numbers from 1 to the input value n. Converting these numbers to strings takes O(n) time. The most significant cost is sorting this list of n strings lexicographically. Sorting algorithms like merge sort or quicksort, which are commonly used in standard library sort functions, have a time complexity of O(n log n) for n elements. Therefore, the dominant operation is the sorting step, and the overall time complexity is O(n log n).

Space Complexity

O(N) – The brute force method creates a list to store all numbers from 1 to N. Sorting this list in place might seem space-efficient, but often sorting algorithms use auxiliary space proportional to the size of the input array. Therefore, the dominant space usage comes from storing the initial list of N numbers, leading to O(N) auxiliary space complexity.

Optimal Solution

Approach

To efficiently find the K-th smallest number in lexicographical order, we'll use a step-by-step counting process instead of generating all possible numbers. We cleverly navigate the number space to skip over large sections we know are too small to contain our target.

Here's how the algorithm would work step-by-step:

Start with the number 1 as a potential starting point.
Count how many numbers exist in the range starting from this point until we reach a number that is bigger than the maximum allowed number or until the next lexicographical number. Essentially, count how many numbers 'belong' to the current 'prefix'.
Compare the count to K. If the count is less than K, it means the K-th number is further down the line so subtract count from K and move to the next lexicographical prefix (e.g., from 1 to 2).
If the count is greater or equal to K, it means the K-th number is within the current prefix. So, move to the next number in the current prefix by adding a '0' to the end (e.g., from 1 to 10) and decrement K by 1.
Repeat steps 2-4 until K becomes 1. The current number is the K-th smallest number.
This process avoids generating and sorting all numbers, significantly speeding up the search.

Code Implementation

def find_kth_number(max_number, k_value):
    current_number = 1

    while k_value > 1:
        # Calculate how many numbers have current_number as a prefix
        numbers_with_prefix = count_numbers_with_prefix(
            max_number, current_number
        )

        # Kth number is in the range starting from current_number
        if numbers_with_prefix >= k_value:
            current_number *= 10
            k_value -= 1

        # Kth number is not within this prefix
        else:
            k_value -= numbers_with_prefix
            current_number += 1

            # Adjust if current_number exceeds max_number
            while current_number % 10 == 0:
                current_number //= 10

    return current_number

def count_numbers_with_prefix(max_number, prefix):
    next_prefix = prefix + 1
    step = 0

    # Count how many numbers between prefix and next prefix
    while prefix <= max_number:
        step += min(max_number + 1, next_prefix) - prefix
        prefix *= 10
        next_prefix *= 10

    return step

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm's time complexity is determined by how many times we iterate through the prefixes. In the worst case, we traverse down the lexicographical tree until we reach a leaf. Each iteration involves calculating the 'count' of nodes under a prefix and then deciding to move horizontally (to the next prefix) or vertically (deeper into a prefix). The number of levels we can go down is limited by the number of digits in 'n'. Therefore, the number of iterations is logarithmic to n (the maximum number itself), making the time complexity O(log n).

Space Complexity

O(1) – The algorithm primarily uses integer variables to track the current number and the remaining K value. No additional data structures like arrays or hash maps are allocated. The space used by these variables is constant and independent of the input value N, representing the maximum number, and K, the rank of the number being searched. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
n or k is zero	If n or k is zero, return 0 as there are no numbers or we're asking for the zeroth smallest.
k is greater than n	If k > n, return -1 (or an appropriate error value) since the kth lexicographical number cannot exist.
n is a single digit number	Handle the case where n is a single-digit number; the k-th smallest number is simply k if k <= n.
k is 1	If k is 1, the result is always 1.
k is close to n	Consider performance implications of reaching close to n using increments; a jump might be faster in some sections.
Integer overflow when calculating steps (number of children)	Use long data type for calculations to avoid potential integer overflow during step calculation.
Very large n	For very large 'n', the number of steps might also be extremely large, so handling of potentially large values is needed.
k is a power of 10	When k is a power of 10, the resulting lexicographical number may be different than initially projected.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` (the upper bound for the numbers) and `k` (the desired lexicographical rank)? What are the maximum possible values for these inputs?
Is `k` guaranteed to be a valid rank, meaning that it will always be within the range of possible numbers formed from 1 to `n`?
What should I return if `k` is greater than the number of integers that can be formed lexicographically from 1 to `n`?
By 'lexicographical order', do you mean string-based lexicographical order (e.g., '10' comes before '2')?
Are `n` and `k` always positive integers?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a list of all numbers from 1 up to the given maximum number.
Think of these numbers as words in a dictionary.
Next, arrange these numbers in the way a dictionary would: alphabetically.
Finally, find the number that is in the K-th position in this sorted dictionary. That number is the answer.

Code Implementation

def find_kth_smallest_lexicographical(maximum_number, k_value):
    # Create a list of all numbers from 1 to maximum_number.
    number_list = [str(number) for number in range(1, maximum_number + 1)]

    # Sort the numbers lexicographically (as strings).
    number_list.sort()

    # Return the k_value-th element in the sorted list.
    # Adjust index because lists are zero-indexed.
    return int(number_list[k_value - 1])

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1 as a potential starting point.
Count how many numbers exist in the range starting from this point until we reach a number that is bigger than the maximum allowed number or until the next lexicographical number. Essentially, count how many numbers 'belong' to the current 'prefix'.
Compare the count to K. If the count is less than K, it means the K-th number is further down the line so subtract count from K and move to the next lexicographical prefix (e.g., from 1 to 2).
If the count is greater or equal to K, it means the K-th number is within the current prefix. So, move to the next number in the current prefix by adding a '0' to the end (e.g., from 1 to 10) and decrement K by 1.
Repeat steps 2-4 until K becomes 1. The current number is the K-th smallest number.
This process avoids generating and sorting all numbers, significantly speeding up the search.

Code Implementation

def find_kth_number(max_number, k_value):
    current_number = 1

    while k_value > 1:
        # Calculate how many numbers have current_number as a prefix
        numbers_with_prefix = count_numbers_with_prefix(
            max_number, current_number
        )

        # Kth number is in the range starting from current_number
        if numbers_with_prefix >= k_value:
            current_number *= 10
            k_value -= 1

        # Kth number is not within this prefix
        else:
            k_value -= numbers_with_prefix
            current_number += 1

            # Adjust if current_number exceeds max_number
            while current_number % 10 == 0:
                current_number //= 10

    return current_number

def count_numbers_with_prefix(max_number, prefix):
    next_prefix = prefix + 1
    step = 0

    # Count how many numbers between prefix and next prefix
    while prefix <= max_number:
        step += min(max_number + 1, next_prefix) - prefix
        prefix *= 10
        next_prefix *= 10

    return step

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n or k is zero	If n or k is zero, return 0 as there are no numbers or we're asking for the zeroth smallest.
k is greater than n	If k > n, return -1 (or an appropriate error value) since the kth lexicographical number cannot exist.
n is a single digit number	Handle the case where n is a single-digit number; the k-th smallest number is simply k if k <= n.
k is 1	If k is 1, the result is always 1.
k is close to n	Consider performance implications of reaching close to n using increments; a jump might be faster in some sections.
Integer overflow when calculating steps (number of children)	Use long data type for calculations to avoid potential integer overflow during step calculation.
Very large n	For very large 'n', the number of steps might also be extremely large, so handling of potentially large values is needed.
k is a power of 10	When k is a power of 10, the resulting lexicographical number may be different than initially projected.