LeetCode 668 - Kth Smallest Number in Multiplication Table

LeetCode Problem 668

Difficulty: 🔴 Hard
Topics: Math, Binary Search

Solution

Problem Understanding

The problem gives us an m x n multiplication table where each cell contains the product of its row index and column index, using 1-based indexing. That means the value at position (i, j) is simply i * j.

For example, when m = 3 and n = 3, the multiplication table looks like this:

	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

If we flatten and sort all values, we get:

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

The task is to return the kth smallest value in this sorted ordering.

An important detail is that duplicate values count separately. For example, the value 2 appears twice in the table above, and both occurrences matter when determining the kth smallest element.

The constraints are extremely important:

• 1 <= m, n <= 3 * 10^4
• 1 <= k <= m * n

A multiplication table can therefore contain up to:

30000 * 30000 = 900,000,000

elements.

This immediately tells us that generating all values explicitly is impossible. Even storing the table would require far too much memory, and sorting hundreds of millions of values would be prohibitively expensive.

The constraints strongly suggest that we need a mathematical or binary-search-based solution instead of direct simulation.

Several edge cases are worth recognizing early:

• Very small tables such as 1 x 1
• Extremely rectangular tables such as 1 x 30000
• Cases where many duplicate values exist
• Cases where k = 1, meaning we need the minimum value
• Cases where k = m * n, meaning we need the maximum value
• Large inputs where brute force would time out immediately

The problem guarantees valid input, so we never need to handle invalid dimensions or out-of-range k.

Approaches

Brute Force Approach

The most straightforward solution is to generate every value in the multiplication table, store them in an array, sort the array, and return the kth element.

For every row i from 1 to m, and every column j from 1 to n, we compute:

i * j

After collecting all values, we sort the array in ascending order and return the element at index k - 1.

This works because sorting produces the exact ordering of the multiplication table values, including duplicates.

However, this approach is completely impractical for the given constraints. The table may contain up to 900 million values. Generating, storing, and sorting that many integers would exceed both memory and time limits.

Key Insight

The crucial observation is that we do not actually need to generate the table.

Instead, we can binary search on the answer itself.

Suppose we guess a number x. We can efficiently determine how many values in the multiplication table are less than or equal to x.

For a fixed row i, the row values are:

i, 2i, 3i, 4i, ...

The count of numbers in this row that are <= x is:

min(n, x // i)

because:

• x // i tells us how many multiples of i fit within x
• we cannot exceed the row length n

Summing this across all rows gives the total number of table values less than or equal to x.

This counting operation allows us to perform binary search over the value range [1, m * n].

If at least k numbers are <= x, then the answer could be x or smaller.

Otherwise, the answer must be larger.

This transforms the problem from impossible explicit generation into efficient counting plus binary search.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n log(m * n))	O(m * n)	Generates and sorts the entire table
Optimal	O(m log(m * n))	O(1)	Binary search on value space with efficient counting

Algorithm Walkthrough

1. Initialize the binary search range.

The smallest possible value in the multiplication table is 1.

The largest possible value is m * n.

We therefore search within:

left = 1
right = m * n

2. Perform binary search on the value range.

At each iteration, compute:

mid = (left + right) // 2

The goal is to determine whether the kth smallest number is less than or equal to mid. 3. Count how many table values are less than or equal to mid.

For each row i from 1 to m:

count += min(n, mid // i)

This works because row i contains:

i, 2i, 3i, ..., ni

and mid // i tells us how many multiples of i are at most mid. 4. Use the count to shrink the search space.

If:

count >= k

then there are already at least k values less than or equal to mid.

That means the answer is not larger than mid, so we move left:

right = mid

Otherwise:

left = mid + 1

because the answer must be larger. 5. Continue until the search converges.

Binary search stops when:

left == right

At that moment, we have found the smallest number such that at least k values are less than or equal to it.

Why it works

The key invariant is that the true answer always remains inside the binary search range.

For any candidate value x, the counting function correctly computes how many multiplication-table entries are <= x.

If fewer than k values are <= x, then x is definitely too small.

If at least k values are <= x, then the answer may be x or smaller.

Because the count function is monotonic, meaning larger x values never decrease the count, binary search is guaranteed to converge to the smallest valid value, which is exactly the kth smallest number.

Python Solution

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def count_less_equal(value: int) -> int:
            count = 0

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

            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

The implementation follows the binary-search strategy directly.

The helper function count_less_equal computes how many numbers in the multiplication table are less than or equal to a given value.

For each row, the expression:

value // row

determines how many multiples of row fit within value.

Since each row has only n columns, we cap the count using:

min(n, value // row)

The binary search maintains a range of possible answers. Whenever the count is large enough, we know the answer is at most mid, so we shrink the right boundary. Otherwise, we increase the left boundary.

Eventually, both pointers converge to the smallest valid number, which is the answer.

Go Solution

func findKthNumber(m int, n int, k int) int {
	countLessEqual := func(value int) int {
		count := 0

		for row := 1; row <= m; row++ {
			count += min(n, value/row)
		}

		return count
	}

	left := 1
	right := m * n

	for left < right {
		mid := (left + right) / 2

		if countLessEqual(mid) >= k {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation mirrors the Python logic closely.

One notable difference is that Go does not provide a built-in min function for integers, so we define our own helper.

Integer division in Go automatically truncates toward zero, which matches the behavior needed for counting multiples.

No additional memory structures are required, so the implementation remains constant-space.

Worked Examples

Example 1

Input:

m = 3
n = 3
k = 5

The multiplication table is:

	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

Sorted values:

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

The 5th smallest value is 3.

Binary Search Trace

left	right	mid	count <= mid	Action
1	9	5	6	move right to 5
1	5	3	5	move right to 3
1	3	2	3	move left to 3

Now:

left = right = 3

Answer:

3

Count Computation for mid = 3

Row	Values	Values <= 3	Count
1	1,2,3	1,2,3	3
2	2,4,6	2	1
3	3,6,9	3	1

Total:

3 + 1 + 1 = 5

Since there are exactly 5 values <= 3, the 5th smallest value is 3.

Example 2

Input:

m = 2
n = 3
k = 6

Table:

	1	2	3
1	1	2	3
2	2	4	6

Sorted values:

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

The 6th smallest value is 6.

Binary Search Trace

left	right	mid	count <= mid	Action
1	6	3	4	move left to 4
4	6	5	5	move left to 6

Now:

left = right = 6

Answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log(m * n))	Binary search performs log(m*n) iterations, each counting across m rows
Space	O(1)	Only a few variables are used

The binary search range spans from 1 to m * n, so the number of iterations is logarithmic in that range.

Inside each iteration, we scan all m rows and compute the count contribution in constant time per row.

No additional arrays, heaps, or hash maps are required, so the memory usage remains constant.

Test Cases

solution = Solution()

# Provided examples
assert solution.findKthNumber(3, 3, 5) == 3  # example 1
assert solution.findKthNumber(2, 3, 6) == 6  # example 2

# Smallest possible table
assert solution.findKthNumber(1, 1, 1) == 1  # single element

# Single row table
assert solution.findKthNumber(1, 10, 7) == 7  # behaves like sorted sequence

# Single column table
assert solution.findKthNumber(10, 1, 4) == 4  # vertical table

# Duplicate-heavy table
assert solution.findKthNumber(3, 3, 4) == 3  # duplicates counted separately

# Maximum element
assert solution.findKthNumber(3, 5, 15) == 15  # largest value in table

# Rectangular table
assert solution.findKthNumber(5, 7, 12) == 6  # non-square table

# Large dimensions with small k
assert solution.findKthNumber(30000, 30000, 1) == 1  # minimum value

# Large dimensions with large k
assert solution.findKthNumber(30000, 30000, 900000000) == 900000000  # maximum value

# Middle-range lookup
assert solution.findKthNumber(10, 10, 50) == 24  # median-ish position

Test Summary

Test	Why
(3,3,5)	Validates standard example
(2,3,6)	Validates largest element lookup
(1,1,1)	Smallest possible input
(1,10,7)	Tests single-row behavior
(10,1,4)	Tests single-column behavior
(3,3,4)	Ensures duplicates are counted correctly
(3,5,15)	Validates maximum position
(5,7,12)	Tests rectangular tables
(30000,30000,1)	Stress test with smallest k
(30000,30000,900000000)	Stress test with largest k
(10,10,50)	General mid-range correctness

Edge Cases

One important edge case is a table with only one row or one column. In these situations, the multiplication table effectively becomes a sorted sequence already. A buggy implementation might incorrectly assume a square table or mishandle row counting. The counting formula still works perfectly because each row contributes either zero or one valid segment.

Another important edge case involves duplicate values. Multiplication tables naturally contain repeated numbers, such as 2 appearing as both 1 * 2 and 2 * 1. A common mistake is to treat values as unique. The problem explicitly counts duplicates separately, and the counting-based binary search naturally handles this because it counts positions, not distinct values.

A third important edge case occurs when k = m * n, meaning we need the largest element in the table. The answer must then be m * n. Some binary search implementations fail due to off-by-one errors near the upper boundary. Using the standard lower-bound binary search pattern with while left < right guarantees correct convergence even at the extremes of the search range.

A final edge case involves extremely large dimensions near the constraint limit. Any approach that explicitly generates the table will fail either from excessive runtime or memory usage. The optimal solution avoids this entirely because it never stores table values and only performs arithmetic counting operations.