Jobs

Interviews

Discussions

Kth Smallest Number in Multiplication Table

Hard

Uber

1 view

Topics:

Binary Search

Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).

Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.

For example:

Consider a multiplication table where m = 3, and n = 3. The table would look like this:

1 2 3
2 4 6
3 6 9

If k = 5, the 5th smallest number in the table is 3.

As another example:

Consider a multiplication table where m = 2, and n = 3. The table would look like this:

1 2 3
2 4 6

If k = 6, the 6th smallest number in the table is 6.

Can you efficiently determine the kth smallest element without explicitly constructing the entire multiplication table?

Kth Smallest Number in Multiplication Table

Hard

Uber

1 view

Topics:

Binary Search

Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).

Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.

For example:

Consider a multiplication table where m = 3, and n = 3. The table would look like this:

1 2 3
2 4 6
3 6 9

If k = 5, the 5th smallest number in the table is 3.

As another example:

Consider a multiplication table where m = 2, and n = 3. The table would look like this:

1 2 3
2 4 6

If k = 6, the 6th smallest number in the table is 6.

Can you efficiently determine the kth smallest element without explicitly constructing the entire multiplication table?

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 maximum values for `m` and `n` (the dimensions of the multiplication table)?
Is `k` guaranteed to be within the bounds of the multiplication table (i.e., 1 <= k <= m * n)?
Are `m` and `n` always positive integers?
Are we looking for the k-th smallest *distinct* number in the table, or can there be duplicates?
Could you provide a small example to illustrate the expected output?

Brute Force Solution

Approach

The problem is about finding a specific number within a multiplication table. The brute force approach simply generates all the numbers in the multiplication table and then sorts them to find the desired one.

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

First, create all the possible products in the multiplication table. For example, if the table is 3x3, calculate 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2, and 3x3.
Next, take all the numbers you just calculated and put them in order from smallest to largest.
Finally, find the number that's in the position you're looking for (the 'kth' smallest number). If you want the 5th smallest, pick the number in the 5th spot.

Code Implementation

def find_kth_number_brute_force(row_size, column_size, k_value):
    multiplication_table = []

    # Generate the multiplication table.
    for row_index in range(1, row_size + 1):
        for column_index in range(1, column_size + 1):
            product = row_index * column_index
            multiplication_table.append(product)

    # Sorting is necessary to find the kth smallest element.
    multiplication_table.sort()

    # Return the kth smallest number.
    return multiplication_table[k_value - 1]

Big(O) Analysis

Time Complexity

O(m*n log(m*n)) – The algorithm first generates all m*n elements of the multiplication table. Then, it sorts these elements to find the kth smallest element. Generating the multiplication table takes O(m*n) time. Sorting the m*n elements takes O(m*n log(m*n)) time. Therefore, the dominant operation is sorting, leading to a total time complexity of O(m*n log(m*n)).

Space Complexity

O(m*n) – The described brute force solution first creates all possible products in the multiplication table, resulting in m*n values. These values are then stored in a list or array for sorting. Therefore, the auxiliary space required is proportional to the size of the multiplication table, which is m*n, where m and n are the dimensions of the table. The space complexity is thus O(m*n).

Optimal Solution

Approach

The most efficient way to find the kth smallest number is to use a method similar to searching in a sorted list, but adapted for the multiplication table. Instead of checking every number, we use a guessing strategy to narrow down the possibilities.

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

First, realize that the numbers in the multiplication table are between 1 and the product of the two input numbers.
Use a strategy similar to a binary search. Start by guessing a number in the middle of this range.
Count how many numbers in the multiplication table are less than or equal to your guess. Do this efficiently by considering each row of the table.
If the count is less than k, it means your guess is too small. Adjust the lower bound of your search to be above your guess.
If the count is greater than or equal to k, it means your guess is either the answer or too big. Adjust the upper bound of your search to be your guess.
Repeat the guessing and counting process, narrowing the range each time, until you find the smallest number that has at least k numbers less than or equal to it.

Code Implementation

def findKthNumber(multiplication_table_height, multiplication_table_width, kth_value):

    left_value = 1
    right_value = multiplication_table_height * multiplication_table_width

    while left_value < right_value:
        middle_value = left_value + (right_value - left_value) // 2
        
        count = 0
        for i in range(1, multiplication_table_height + 1):
            count += min(middle_value // i, multiplication_table_width)

            # If count is less than kth_value, adjust search.
        if count < kth_value:
            left_value = middle_value + 1

        else:
            # If count is >= kth_value, adjust search.
            right_value = middle_value

    return left_value

Big(O) Analysis

Time Complexity

O(m log(m*n)) – The algorithm performs a binary search over the range of numbers from 1 to m*n, where m and n are the dimensions of the multiplication table. The binary search takes O(log(m*n)) iterations. In each iteration, we count the number of elements in the multiplication table that are less than or equal to the mid-point. Counting involves iterating through 'm' rows, and in each row, computing how many numbers are less than or equal to mid/row_number (which is O(1)). Therefore, counting takes O(m) time. So the overall time complexity is O(m * log(m*n)).

Space Complexity

O(1) – The algorithm uses a binary search approach that primarily involves updating lower and upper bound variables for the search range. It also uses a counter variable to track the number of elements less than or equal to the guess. These variables consume a constant amount of extra space, irrespective of the input values m, n, and k. Therefore, the space complexity remains constant.

Edge Cases

Case	How to Handle
m or n is zero	Return 0 immediately as a zero-sized table contains no elements.
k is zero or negative	Return an error or throw an exception as the kth smallest element is not defined for non-positive k.
k is greater than m * n	Return the largest element in the table (m * n) since k exceeds the number of elements.
m or n is 1	The multiplication table collapses to a single row or column, simplifying the search to finding the kth smallest in a linear sequence.
Large m and n values (close to integer limits)	Potential integer overflow during calculations (m * n) should be handled by using a 64-bit integer or checking limits.
k is close to 1	Binary search should efficiently converge to the correct element near the start of the sorted sequence.
k is close to m * n	Binary search should efficiently converge to the correct element near the end of the sorted sequence.
Multiplication table contains duplicate values clustered together	The binary search and counting function within should still function correctly because it counts numbers less than or equal, handling duplicates naturally.

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 maximum values for `m` and `n` (the dimensions of the multiplication table)?
Is `k` guaranteed to be within the bounds of the multiplication table (i.e., 1 <= k <= m * n)?
Are `m` and `n` always positive integers?
Are we looking for the k-th smallest *distinct* number in the table, or can there be duplicates?
Could you provide a small example to illustrate the expected output?

Brute Force Solution

Approach

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

First, create all the possible products in the multiplication table. For example, if the table is 3x3, calculate 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2, and 3x3.
Next, take all the numbers you just calculated and put them in order from smallest to largest.
Finally, find the number that's in the position you're looking for (the 'kth' smallest number). If you want the 5th smallest, pick the number in the 5th spot.

Code Implementation

def find_kth_number_brute_force(row_size, column_size, k_value):
    multiplication_table = []

    # Generate the multiplication table.
    for row_index in range(1, row_size + 1):
        for column_index in range(1, column_size + 1):
            product = row_index * column_index
            multiplication_table.append(product)

    # Sorting is necessary to find the kth smallest element.
    multiplication_table.sort()

    # Return the kth smallest number.
    return multiplication_table[k_value - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, realize that the numbers in the multiplication table are between 1 and the product of the two input numbers.
Use a strategy similar to a binary search. Start by guessing a number in the middle of this range.
Count how many numbers in the multiplication table are less than or equal to your guess. Do this efficiently by considering each row of the table.
If the count is less than k, it means your guess is too small. Adjust the lower bound of your search to be above your guess.
If the count is greater than or equal to k, it means your guess is either the answer or too big. Adjust the upper bound of your search to be your guess.
Repeat the guessing and counting process, narrowing the range each time, until you find the smallest number that has at least k numbers less than or equal to it.

Code Implementation

def findKthNumber(multiplication_table_height, multiplication_table_width, kth_value):

    left_value = 1
    right_value = multiplication_table_height * multiplication_table_width

    while left_value < right_value:
        middle_value = left_value + (right_value - left_value) // 2
        
        count = 0
        for i in range(1, multiplication_table_height + 1):
            count += min(middle_value // i, multiplication_table_width)

            # If count is less than kth_value, adjust search.
        if count < kth_value:
            left_value = middle_value + 1

        else:
            # If count is >= kth_value, adjust search.
            right_value = middle_value

    return left_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
m or n is zero	Return 0 immediately as a zero-sized table contains no elements.
k is zero or negative	Return an error or throw an exception as the kth smallest element is not defined for non-positive k.
k is greater than m * n	Return the largest element in the table (m * n) since k exceeds the number of elements.
m or n is 1	The multiplication table collapses to a single row or column, simplifying the search to finding the kth smallest in a linear sequence.
Large m and n values (close to integer limits)	Potential integer overflow during calculations (m * n) should be handled by using a 64-bit integer or checking limits.
k is close to 1	Binary search should efficiently converge to the correct element near the start of the sorted sequence.
k is close to m * n	Binary search should efficiently converge to the correct element near the end of the sorted sequence.
Multiplication table contains duplicate values clustered together	The binary search and counting function within should still function correctly because it counts numbers less than or equal, handling duplicates naturally.