Solution Approach

We use the standard binary search template with first_true_index to find the kth smallest element.

Binary Search Setup:

• left = 1: minimum possible value in the table
• right = m * n: maximum possible value in the table
• first_true_index = -1: tracks the first value where count >= k

Feasible Condition: For any value mid, we count how many elements in the multiplication table are ≤ mid. If this count is >= k, then mid could be our answer (or the answer is smaller). This creates the monotonic pattern: false, false, ..., true, true, true.

Counting Elements ≤ mid: For each row i (from 1 to m), the elements are i, 2i, 3i, ..., n*i. The count of elements ≤ mid in row i is min(mid // i, n):

• mid // i gives how many multiples of i are ≤ mid
• We cap at n because each row has at most n elements

Binary Search Template:

while left <= right:
    mid = (left + right) // 2
    count = sum(min(mid // row, n) for row in range(1, m + 1))

    if count >= k:  # Feasible: kth element is at most mid
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

Why the Result Exists in the Table: The binary search finds the smallest value where count >= k. This value is guaranteed to exist in the multiplication table because:

• If mid is in the table and count(mid) >= k while count(mid-1) < k, then mid is exactly the kth smallest
• The template converges to this exact boundary

The time complexity is O(m * log(m * n)) - O(log(m * n)) iterations with O(m) counting each. Space complexity is O(1).

Example Walkthrough

Let's trace through the binary search template with m = 3, n = 3, k = 5.

Setup:

• Multiplication table:

1  2  3
2  4  6
3  6  9

• Sorted values: [1, 2, 2, 3, 3, 4, 6, 6, 9]
• Looking for 5th element (should be 3)

Initial state:

• left = 1, right = 9, first_true_index = -1
• Feasible condition: count of elements ≤ mid is >= 5

Iteration 1:

• mid = (1 + 9) // 2 = 5
• Count elements ≤ 5:
  • Row 1: min(5/1, 3) = 3 elements (1, 2, 3)
  • Row 2: min(5/2, 3) = 2 elements (2, 4)
  • Row 3: min(5/3, 3) = 1 element (3)
  • Total = 6
• Is 6 >= 5? Yes → Feasible
• Update: first_true_index = 5, right = 4

Iteration 2:

• left = 1, right = 4
• mid = (1 + 4) // 2 = 2
• Count elements ≤ 2:
  • Row 1: min(2/1, 3) = 2 elements (1, 2)
  • Row 2: min(2/2, 3) = 1 element (2)
  • Row 3: min(2/3, 3) = 0 elements
  • Total = 3
• Is 3 >= 5? No → Not feasible
• Update: left = 3

Iteration 3:

• left = 3, right = 4
• mid = (3 + 4) // 2 = 3
• Count elements ≤ 3:
  • Row 1: min(3/1, 3) = 3 elements
  • Row 2: min(3/2, 3) = 1 element
  • Row 3: min(3/3, 3) = 1 element
  • Total = 5
• Is 5 >= 5? Yes → Feasible
• Update: first_true_index = 3, right = 2

Iteration 4:

• left = 3, right = 2
• Loop ends: left > right

Result:

• first_true_index = 3
• The 5th smallest element is 3

The template correctly finds the boundary where count first reaches k.

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. Using Wrong Binary Search Template Variant

The Pitfall: A common mistake is using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Incorrect (non-standard template):

while left < right:
    mid = (left + right) // 2
    if count >= k:
        right = mid
    else:
        left = mid + 1
return left

Correct (standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if count >= k:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

The standard template with first_true_index clearly tracks the answer and handles edge cases consistently.

2. Incorrect Counting Logic

The Pitfall: Not considering the table boundaries when counting:

Incorrect:

count += mid // row  # Missing the min() with n

Why This Fails: Each row has exactly n elements. Without min(mid // row, n), we count more elements than exist. If mid = 100, row = 1, and n = 5, we'd count 100 elements instead of 5.

Correct:

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

3. Using 0-Based Indexing for Rows

Incorrect:

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

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

Correct:

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

In languages with fixed integer sizes, calculating left + right can overflow.

Safe Approach:

mid = left + (right - left) // 2  # Prevents overflow