LeetCode 668: Kth Smallest Number in Multiplication Table

Problem Restatement

We are given three integers m, n, and k.

Imagine an m x n multiplication table where each cell is:

table[i][j] = i * j

using 1-based indexing.

We need to return the kth smallest number in this multiplication table.

The table may contain duplicates, and duplicates count separately.

For example, in a 3 x 3 table:

1  2  3
2  4  6
3  6  9

the sorted values are:

[1, 2, 2, 3, 3, 4, 6, 6, 9]

The 5th smallest value is 3. The official statement gives this same task: return the kth smallest element in an m x n multiplication table.

Input and Output

Example function shape:

def findKthNumber(m: int, n: int, k: int) -> int:
    ...

Examples

Consider:

m = 3
n = 3
k = 5

The table is:

1  2  3
2  4  6
3  6  9

Sorted values:

[1, 2, 2, 3, 3, 4, 6, 6, 9]

The 5th value is:

3

So the answer is 3.

Another example:

m = 2
n = 3
k = 6

The table is:

1  2  3
2  4  6

Sorted values:

[1, 2, 2, 3, 4, 6]

The 6th value is:

6

So the answer is 6.

First Thought: Build and Sort the Table

A direct solution is:

1. Generate every product i * j.
2. Sort all products.
3. Return the element at index k - 1.

This is simple, but the constraints allow m and n up to 3 * 10^4, so the table can contain up to 9 * 10^8 entries. Building the full table is too expensive.

We need to find the value without materializing the table.

Key Insight

We can binary search on the answer.

The smallest possible value is:

1

The largest possible value is:

m * n

For any candidate value x, we can count how many table entries are less than or equal to x.

If at least k entries are <= x, then the kth smallest value is at most x.

If fewer than k entries are <= x, then the kth smallest value is greater than x.

This gives a monotonic condition suitable for binary search.

Counting Values Less Than or Equal to x

Consider row i.

The row contains:

i, 2i, 3i, ..., n*i

We need to count how many of these values are <= x.

That count is:

min(x // i, n)

Why?

x // i tells us how many multiples of i are at most x.

But the row only has n columns, so the count cannot exceed n.

Therefore, the total count is:

sum(min(x // i, n) for i in range(1, m + 1))

This counting formula is the core of the standard solution.

Algorithm

Use binary search over values.

1. Set left = 1.
2. Set right = m * n.
3. While left < right:
   • Let mid = (left + right) // 2.
   • Count how many table values are <= mid.
   • If the count is at least k, move right = mid.
   • Otherwise, move left = mid + 1.
4. Return left.

The binary search finds the smallest value x such that at least k table entries are <= x.

That value is exactly the kth smallest number.

Correctness

Define count(x) as the number of entries in the multiplication table that are less than or equal to x.

As x increases, count(x) never decreases. This monotonic property allows binary search.

If count(x) >= k, then there are already at least k entries no larger than x, so the kth smallest value is less than or equal to x.

If count(x) < k, then fewer than k entries are no larger than x, so the kth smallest value must be greater than x.

The algorithm searches for the smallest value where count(x) >= k.

By definition, that smallest value is exactly the kth smallest element in the table.

The row-count formula is correct because row i contains the multiples i, 2i, ..., n*i, and exactly min(x // i, n) of them are at most x.

Therefore, the algorithm returns the correct kth smallest value.

Complexity

We can also iterate over the smaller dimension by swapping m and n, which gives:

O(min(m, n) * log(mn))

Implementation

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        if m > n:
            m, n = n, m

        def count_less_equal(x: int) -> int:
            count = 0

            for row in range(1, m + 1):
                count += min(x // row, n)

            return count

        left = 1
        right = m * n

        while left < right:
            mid = (left + right) // 2

            if count_less_equal(mid) >= k:
                right = mid
            else:
                left = mid + 1

        return left

Code Explanation

We optionally swap dimensions:

if m > n:
    m, n = n, m

This makes the counting loop run over the smaller dimension.

The helper function counts how many values are at most x:

def count_less_equal(x: int) -> int:

For each row:

count += min(x // row, n)

x // row counts how many multiples of row fit under x.

n caps that number by the row length.

The binary search range is:

left = 1
right = m * n

At each step:

mid = (left + right) // 2

If mid is large enough to cover at least k entries:

if count_less_equal(mid) >= k:
    right = mid

then the answer may be mid or smaller.

Otherwise:

left = mid + 1

the answer must be larger.

When the loop ends, left is the smallest valid value.

Testing

def run_tests():
    s = Solution()

    assert s.findKthNumber(3, 3, 5) == 3
    assert s.findKthNumber(2, 3, 6) == 6

    assert s.findKthNumber(1, 10, 7) == 7
    assert s.findKthNumber(10, 1, 7) == 7

    assert s.findKthNumber(3, 3, 1) == 1
    assert s.findKthNumber(3, 3, 9) == 9

    assert s.findKthNumber(4, 4, 8) == 4

    print("all tests passed")

run_tests()

Test meaning: