Problem Description

You're given a multiplication table of size m x n, where each cell at position [i][j] contains the product i * j (using 1-based indexing). For example, a 3x3 multiplication table would look like:

1  2  3
2  4  6
3  6  9

The task is to find the kth smallest element when all values in this multiplication table are considered in sorted order.

Input:

• m: number of rows in the multiplication table
• n: number of columns in the multiplication table
• k: the position of the element to find (1-indexed)

Output:

• The kth smallest value in the multiplication table

Example: For a 3x3 table with k = 5, the values in sorted order would be: [1, 2, 2, 3, 3, 4, 6, 6, 9]. The 5th smallest element is 3.

The solution uses binary search on the value range [1, m*n]. For each candidate value mid, it counts how many elements in the multiplication table are less than or equal to mid. This is done by iterating through each row i and calculating min(mid // i, n), which gives the count of elements in row i that are ≤ mid. If the total count is at least k, the answer is at most mid; otherwise, it must be larger than mid. The binary search continues until it converges on the exact kth smallest value.

Intuition

The key insight is that we don't need to generate the entire multiplication table to find the kth smallest element. Instead, we can use binary search on the possible values.

Think about it this way: the smallest possible value in the table is 1 (at position [1][1]), and the largest is m * n (at position [m][n]). The answer must be somewhere in this range.

For any given value x, we can efficiently count how many elements in the multiplication table are less than or equal to x without generating the table. How? For each row i, the elements are i, 2i, 3i, ..., n*i. The number of elements ≤ x in row i is simply min(x // i, n) - we divide x by i to see how many multiples of i are ≤ x, but cap it at n since each row has only n elements.

This counting ability enables a binary search strategy:

• If we pick a value mid and find that there are at least k elements ≤ mid, then our answer is at most mid
• If there are fewer than k elements ≤ mid, then our answer must be greater than mid

The beauty of this approach is that binary search will naturally converge to a value that actually exists in the table. Even though we're searching through all integers in the range [1, m*n], the final answer will always be a valid product that appears in the multiplication table because we're looking for the smallest value where the count reaches k.

Learn more about Math and Binary Search patterns.

Solution Approach

The implementation uses binary search to find the kth smallest element efficiently:

1. Initialize Search Range:

left, right = 1, m * n

We set the search boundaries to the minimum possible value (1) and maximum possible value (m * n) in the multiplication table.

2. Binary Search Loop:

while left < right:
    mid = (left + right) >> 1

We continue searching while left < right. The midpoint is calculated using bit shift (>> 1) which is equivalent to dividing by 2.

3. Count Elements ≤ mid:

cnt = 0
for i in range(1, m + 1):
    cnt += min(mid // i, n)

For each row i (from 1 to m), we count how many elements are less than or equal to mid:

• mid // i gives us how many multiples of i are ≤ mid
• We take min(mid // i, n) because each row has at most n elements
• We accumulate these counts across all rows

4. Adjust Search Range:

if cnt >= k:
    right = mid
else:
    left = mid + 1

• If cnt >= k, it means there are at least k elements ≤ mid, so our answer is at most mid. We move right to mid.
• If cnt < k, it means there are fewer than k elements ≤ mid, so our answer must be greater than mid. We move left to mid + 1.

5. Return Result:

return left

When the loop ends, left equals right, and this value is our answer - the kth smallest element in the multiplication table.

The time complexity is O(m * log(m * n)) where the log factor comes from binary search and we spend O(m) time counting in each iteration. The space complexity is O(1) as we only use a few variables.

Example Walkthrough

Let's walk through finding the 5th smallest element in a 3×3 multiplication table.

Setup:

• m = 3, n = 3, k = 5
• The multiplication table looks like:

1  2  3
2  4  6
3  6  9

• Values in sorted order: [1, 2, 2, 3, 3, 4, 6, 6, 9]
• We're looking for the 5th element, which should be 3

Binary Search Process:

Iteration 1:

• left = 1, right = 9
• mid = (1 + 9) / 2 = 5
• Count elements ≤ 5:
  • Row 1: min(5/1, 3) = min(5, 3) = 3 elements (1, 2, 3)
  • Row 2: min(5/2, 3) = min(2, 3) = 2 elements (2, 4)
  • Row 3: min(5/3, 3) = min(1, 3) = 1 element (3)
  • Total count = 3 + 2 + 1 = 6
• Since 6 ≥ 5, update right = 5

Iteration 2:

• left = 1, right = 5
• mid = (1 + 5) / 2 = 3
• Count elements ≤ 3:
  • Row 1: min(3/1, 3) = min(3, 3) = 3 elements (1, 2, 3)
  • Row 2: min(3/2, 3) = min(1, 3) = 1 element (2)
  • Row 3: min(3/3, 3) = min(1, 3) = 1 element (3)
  • Total count = 3 + 1 + 1 = 5
• Since 5 ≥ 5, update right = 3

Iteration 3:

• left = 1, right = 3
• mid = (1 + 3) / 2 = 2
• Count elements ≤ 2:
  • Row 1: min(2/1, 3) = min(2, 3) = 2 elements (1, 2)
  • Row 2: min(2/2, 3) = min(1, 3) = 1 element (2)
  • Row 3: min(2/3, 3) = min(0, 3) = 0 elements
  • Total count = 2 + 1 + 0 = 3
• Since 3 < 5, update left = 3

Final Result:

• left = 3, right = 3
• Loop terminates, return 3

The algorithm correctly identifies that 3 is the 5th smallest element. Notice how we never generated the full table - we only counted how many elements were less than or equal to our candidate values, making this approach much more efficient than sorting all m×n elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * log(m * n))

The binary search runs from 1 to m * n, which means the search space has size m * n. Binary search takes O(log(m * n)) iterations to converge.

For each iteration of the binary search, we need to count how many elements in the multiplication table are less than or equal to mid. This counting process involves a loop that runs m times (from 1 to m), and for each iteration i, we calculate min(mid // i, n) which takes O(1) time.

Therefore, the total time complexity is O(m * log(m * n)).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables left, right, mid, cnt, and the loop variable i. No additional data structures that scale with input size are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Binary Search Boundary Update

A common mistake is incorrectly updating the binary search boundaries, particularly setting right = mid - 1 when count >= k:

Incorrect Implementation:

if count >= k:
    right = mid - 1  # WRONG! This might skip the actual answer
else:
    left = mid + 1

Why This Fails: When count >= k, mid could be the exact answer. Setting right = mid - 1 would exclude it from the search range. For example, if we're looking for the 5th smallest element and mid = 3 gives us exactly 5 elements ≤ 3, then 3 is our answer. But setting right = 2 would make us miss it.

Correct Approach:

if count >= k:
    right = mid  # Keep mid in the search range as potential answer
else:
    left = mid + 1

2. Incorrect Counting Logic

Another pitfall is misunderstanding how to count elements in each row:

Incorrect Implementation:

# Wrong: Not considering the table boundaries
count += mid // row  # Missing the min() with n

Why This Fails: Each row has exactly n elements. Without min(mid // row, n), we might count more elements than actually exist in a row. For instance, if mid = 100, row = 1, and n = 5, we'd incorrectly count 100 elements in the first row when there are only 5.

Correct Approach:

count += min(mid // row, n)  # Ensures we don't count beyond table boundaries

3. Using 0-Based Indexing for Rows

Incorrect Implementation:

for row in range(m):  # Wrong: starts from 0
    count += min(mid // (row + 1), n)  # Or forgetting to add 1

Why This Fails: The multiplication table uses 1-based indexing. Starting from row 0 would cause division by zero or incorrect calculations.

Correct Approach:

for row in range(1, m + 1):  # Start from 1, go up to m inclusive
    count += min(mid // row, n)

4. Integer Overflow in Large Inputs

While Python handles large integers automatically, in other languages or when optimizing:

Potential Issue:

mid = (left + right) // 2  # Could overflow in other languages

Safe Approach:

mid = left + (right - left) // 2  # Prevents overflow
# Or in Python, bit shift is also safe and efficient:
mid = (left + right) >> 1