Kth Smallest Number in Multiplication Table solution and explanation
Google
9 more videos on this problem
668. Kth Smallest Number in Multiplication Table Leetcode Daily ChallengeCode with Alisha · 20:24 · 8K views
Kth Smallest Number in Multiplication Table |Leetcode 668|Live coding session 🔥| Range Binary SearchCoding Decoded · 9:55 · 4K views
668. Kth Smallest Number in Multiplication Table | Binary Search Series | Coders CampCoders Camp · 9:25 · 3K views
Daily Leetcode #595: Nov 16, 2021 - 668. Kth Smallest Number in Multiplication TableProgramming Live with Larry · 18:56 · 824 views
Leetcode [668] Kth Smallest Number in Multiplication TableSDE Skills · 21:47 · 788 views
Problem of the Day: Kth Smallest Number in Multiplication Table | Must-Solve for CodersSchool of AI · 41:07 · 683 views
668. Kth Smallest Number in Multiplication Table (Leetcode Hard)Programming Live with Larry · 46:27 · 613 views
Leetcode 668: Kth Smallest Number in Multiplication TableExtremeProgrammer · 0:54 · 429 views
Kth Smallest Number in Multiplication Table | Leetcode 668 | GFG | BInary SearchTejpratap Pandey · 18:17 · 410 views
[RUBRIK INTERVIEW QUESTION] Kth Smallest Number Multiplication Table | LeetCode | Solution ExplainedTanishq Chaudhary · 13:40 · 2K views
The problem
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 * 1041 <= 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.
def count_less_equal(m, n, x):
count = 0
for i in range(1, m + 1):
count += min(x // i, n)
return count
def find_kth_number(m, n, k):
low, high = 1, m * n
while low < high:
mid = (low + high) // 2
if count_less_equal(m, n, mid) < k:
low = mid + 1
else:
high = mid
return low
print(find_kth_number(3, 3, 5)) # Output: 3class Solution {
public int countLessOrEqual(int m, int n, int x) {
int count = 0;
for (int i = 1; i <= m; i++) {
count += Math.min(x / i, n);
}
return count;
}
public int findKthNumber(int m, int n, int k) {
int low = 1, high = m * n;
while (low < high) {
int mid = low + (high - low) / 2;
if (countLessOrEqual(m, n, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.findKthNumber(3, 3, 5)); // Output: 3
}
}#include <iostream>
#include <vector>
int countLessOrEqual(int m, int n, int x) {
int count = 0;
for (int i = 1; i <= m; ++i) {
count += std::min(x / i, n);
}
return count;
}
int findKthNumber(int m, int n, int k) {
int low = 1, high = m * n;
while (low < high) {
int mid = low + (high - low) / 2;
if (countLessOrEqual(m, n, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
int main() {
int m = 3, n = 3, k = 5;
std::cout << findKthNumber(m, n, k) << std::endl; // Output: 3
return 0;
}function countLessOrEqual(m, n, x) {
let count = 0;
for (let i = 1; i <= m; i++) {
count += Math.min(Math.floor(x / i), n);
}
return count;
}
function findKthNumber(m, n, k) {
let low = 1, high = m * n;
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (countLessOrEqual(m, n, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
console.log(findKthNumber(3, 3, 5)); // Output: 3#include <stdio.h>
int countLessOrEqual(int m, int n, int x) {
int count = 0;
for (int i = 1; i <= m; i++) {
count += (x / i < n) ? x / i : n;
}
return count;
}
int findKthNumber(int m, int n, int k) {
int low = 1, high = m * n;
while (low < high) {
int mid = low + (high - low) / 2;
if (countLessOrEqual(m, n, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
int main() {
int m = 3, n = 3, k = 5;
printf("%d\n", findKthNumber(m, n, k)); // Output: 3
return 0;
}using System;
class Solution {
public int CountLessOrEqual(int m, int n, int x) {
int count = 0;
for (int i = 1; i <= m; i++) {
count += Math.Min(x / i, n);
}
return count;
}
public int FindKthNumber(int m, int n, int k) {
int low = 1, high = m * n;
while (low < high) {
int mid = low + (high - low) / 2;
if (CountLessOrEqual(m, n, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.FindKthNumber(3, 3, 5)); // Output: 3
}
}In this Python solution, we use binary search to find the kth smallest number in the multiplication table. A helper function `count_less_equal` checks the number of multiples less than or equal to a given number, which helps guide the search.
Time Complexity: O(m * log(m * n))
Space Complexity: O(1)
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.
import heapq
def find_kth_number(m, n, k):
min_heap = [(i, i) for i in range(1, m + 1)]
heapq.heapify(min_heap)
count = 0
while min_heap:
val, base = heapq.heappop(min_heap)
count += 1
if count == k:
return val
if val + base <= base * n:
heapq.heappush(min_heap, (val + base, base))
print(find_kth_number(3, 3, 5)) # Output: 3#include <iostream>
#include <queue>
#include <vector>
struct Comparator {
bool operator()(std::pair<int, int> &a, std::pair<int, int> &b) {
return a.first > b.first;
}
};
int findKthNumber(int m, int n, int k) {
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Comparator> minHeap;
for (int i = 1; i <= m; ++i)
minHeap.push({i, 1});
int count = 0, ans = 0;
while (!minHeap.empty() && count < k) {
auto elem = minHeap.top();
minHeap.pop();
++count;
ans = elem.first;
if (elem.second < n) {
minHeap.push({elem.first + elem.first / elem.second, elem.second + 1});
}
}
return ans;
}
int main() {
int m = 3, n = 3, k = 5;
std::cout << findKthNumber(m, n, k) << std::endl; // Output: 3
return 0;
}This Python solution utilizes a min-heap to access elements of the multiplication table in increasing order. We initially fill the heap with the first multiple of each row index and continually add the next multiple for extraction.
Time Complexity: O(k log m)
Space Complexity: O(m)
Approach 3: Default Approach
func findKthNumber(m int, n int, k int) int {
left, right := 1, m*n
for left < right {
mid := (left + right) >> 1
cnt := 0
for i := 1; i <= m; i++ {
cnt += min(mid/i, n)
}
if cnt >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search Method | Time Complexity: O(m * log(m * n)) |
| Priority Queue (Heap) Method | Time Complexity: O(k log m) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Value Range | O(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 Queue | O(k log m) | O(m) | Useful when k is relatively small or when applying the k-way merge pattern across sorted rows. |
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.