Skip to main content
Talentd

Kth Smallest Number in Multiplication Table - Solution & Explanation

HardMathBinary Search12 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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.

 

Example 1:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6th smallest number is 6.

 

Constraints:

  • 1 <= m, n <= 3 * 104
  • 1 <= k <= m * n

Approach Overview

Problem Overview: You are given an m x n multiplication table where the value at (i, j) is i * j. The task is to return the k-th smallest number among all values in the table without explicitly building the entire matrix.

Approach 1: Binary Search on Value Range (Time: O(m log(mn)), Space: O(1))

The key observation: the multiplication table is sorted both row-wise and column-wise. Instead of generating all values, search over the numeric range [1, m * n]. For a candidate value mid, count how many numbers in the table are ≤ mid. Each row i contributes min(n, mid / i) elements. Summing this for i = 1..m gives the count in O(m). If the count is smaller than k, move the search right; otherwise move left. This monotonic property makes binary search ideal. The approach avoids storing the table and directly pinpoints the kth value.

The counting step relies on simple division and iteration, making the method efficient even when m and n are up to 30,000. This technique is common in problems where the search space is numeric rather than index-based. The multiplication table structure combined with math reasoning enables fast counting.

Approach 2: Min Heap / Priority Queue (Time: O(k log m), Space: O(m))

Another way is to treat each row of the multiplication table as a sorted list: i, 2i, 3i, ... , ni. Insert the first element of each row (i * 1) into a min heap. Repeatedly pop the smallest element and push the next value from the same row (i * (j + 1)). After performing k extractions, the last popped value is the answer.

This technique mirrors the classic "merge k sorted lists" pattern. Each heap node stores the value along with its row index and column multiplier. While straightforward, it becomes slower when k is large because every step performs heap operations. Memory usage also grows with the number of rows pushed into the heap.

Recommended for interviews: Binary search on the value range is the expected solution. Interviewers want to see the insight that you can count how many numbers ≤ x without constructing the table. The heap approach demonstrates understanding of sorted structures, but the binary search method shows stronger algorithmic optimization.

Approach 1: Binary Search Method

The general idea is to use binary search to find the kth smallest element in the multiplication table. The key observation is that for a candidate number X, we can count how many numbers in the multiplication table are less than or equal to X, without constructing the entire table explicitly. Counting these numbers can be efficiently done by iterating over the rows and determining the highest multiple that does not exceed X.

This C solution implements the binary search technique to find the kth smallest number in the multiplication table. The function `countLessOrEqual` computes how many numbers are less than or equal to the given value x. In the main logic, binary search narrows down the potential candidates for the kth smallest number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 2: Priority Queue (Heap) Method

This approach uses a min-heap (priority queue) to keep track of the smallest unseen elements in the multiplication table. By continuously adding the next minimum elements from the rows, we can extract them in order until we reach the kth smallest element.

This C++ code uses a min-heap to track the smallest values efficiently. We insert initial multiples from each row into the heap and extract the smallest at each step, pushing the next element from the same row.

Code

C++Python

C++

Python

Complexity

Time Complexity: O(k log m)
Space Complexity: O(m)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Method

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

Priority Queue (Heap) Method

Time Complexity: O(k log m)
Space Complexity: O(m)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search on Value RangeO(m log(mn))O(1)Best general solution for large tables. Avoids generating the matrix and scales well when m and n are large.
Min Heap / Priority QueueO(k log m)O(m)Useful when k is relatively small or when applying the k-way merge pattern across sorted rows.

Video Solution

668. Kth Smallest Number in Multiplication Table Leetcode Daily Challenge • Code with Alisha • 8,231 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Smallest Number in Multiplication Table easy or hard?
LeetCode classifies this problem as Hard because the optimal solution requires recognizing binary search on the answer space. The implementation itself is relatively short, but identifying the counting strategy inside the multiplication table requires strong problem-solving insight.
Kth Smallest Number in Multiplication Table Python/Java solution
The binary search approach is language agnostic and easy to implement in Python, Java, C++, C#, C, or JavaScript. The algorithm repeatedly checks how many numbers are ≤ mid using division and adjusts the search bounds until the kth value is found.
How to solve Kth Smallest Number in Multiplication Table in O(m log(mn))?
Use binary search on the numeric range from 1 to m*n. For each mid value, count elements ≤ mid by summing min(n, mid / i) for every row i from 1 to m. If the count is smaller than k, move the search range right; otherwise move left. The smallest value that satisfies count ≥ k is the answer.
What is the best approach for Kth Smallest Number in Multiplication Table?
Binary search on the value range is the most efficient approach. Instead of generating the entire multiplication table, you binary search between 1 and m*n and count how many table values are ≤ mid. This counting step runs in O(m), giving an overall complexity of O(m log(mn)) with O(1) space.
Is Kth Smallest Number in Multiplication Table asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving binary search on the answer space. Variants of this technique appear in interviews at companies such as Google, Amazon, and Meta, especially in questions about kth smallest elements in sorted structures or matrices.
What data structure is used in Kth Smallest Number in Multiplication Table?
The optimal approach mainly uses binary search with simple arithmetic counting, requiring no additional data structures. An alternative method uses a min heap (priority queue) to simulate merging sorted rows of the multiplication table.
What is the time complexity of Kth Smallest Number in Multiplication Table?
The optimal binary search solution runs in O(m log(mn)) time and O(1) space. Each binary search step counts how many numbers are ≤ mid by iterating through all rows and using division to determine valid column counts.

Ready to solve this problem?

Practice Kth Smallest Number in Multiplication Table with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find K-th Smallest Pair Distance

Next

K-th Smallest Prime Fraction