Approach #1: Brute Force [Memory Limit Exceeded]
Intuition and Algorithm
Create the multiplication table and sort it, then take the kth element.
Python
class Solution(object):
def findKthNumber(self, m, n, k):
table = [i*j for i in range(1, m+1) for j in range(1, n+1)]
table.sort()
return table[k1]
Java
class Solution {
public int findKthNumber(int m, int n, int k) {
int[] table = new int[m*n];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
table[(i  1) * n + j  1] = i * j;
}
}
Arrays.sort(table);
return table[k1];
}
}
Complexity Analysis

Time Complexity: $$O(mn)$$ to create the table, and $$O(mn\log(m*n))$$ to sort it.

Space Complexity: $$O(m*n)$$ to store the table.
Approach #2: Next Heap [Time Limit Exceeded]
Intuition
Maintain a heap of the smallest unused element of each row. Then, finding the next element is a pop operation on the heap.
Algorithm
Our heap
is going to consist of elements (val, root)
, where val
is the next unused value of that row, and root
was the starting value of that row.
We will repeatedly find the next lowest element in the table. To do this, we pop from the heap. Then, if there's a next lowest element in that row, we'll put that element back on the heap.
Python
class Solution(object):
def findKthNumber(self, m, n, k):
heap = [(i, i) for i in range(1, m+1)]
heapq.heapify(heap)
for _ in xrange(k):
val, root = heapq.heappop(heap)
nxt = val + root
if nxt <= root * n:
heapq.heappush(heap, (nxt, root))
return val
Java
class Solution {
public int findKthNumber(int m, int n, int k) {
PriorityQueue<Node> heap = new PriorityQueue<Node>(m,
Comparator.<Node> comparingInt(node > node.val));
for (int i = 1; i <= m; i++) {
heap.offer(new Node(i, i));
}
Node node = null;
for (int i = 0; i < k; i++) {
node = heap.poll();
int nxt = node.val + node.root;
if (nxt <= node.root * n) {
heap.offer(new Node(nxt, node.root));
}
}
return node.val;
}
}
class Node {
int val;
int root;
public Node(int v, int r) {
val = v;
root = r;
}
}
Complexity Analysis

Time Complexity: $$O(k * m \log m) = O(m^2 n \log m)$$. Our initial heapify operation is $O(m)$. Afterwards, each pop and push is $$O(m \log m)$$, and our outer loop is $$O(k) = O(m*n)$$

Space Complexity: $$O(m)$$. Our heap is implemented as an array with $$m$$ elements.
Approach #3: Binary Search [Accepted]
Intuition
As k
and m*n
are up to $$9 * 10^8$$, linear solutions will not work. This motivates solutions with \log
complexity, such as binary search.
Algorithm
Let's binary search for the answer A
.
Say enough(x)
is true if and only if there are k
or more values in the multiplication table that are less than or equal to x
. Colloquially, enough
describes whether x
is large enough to be the kth
value in the multiplication table.
Then (for our answer A
), whenever x >= A
, enough(x)
is True
; and whenever x < A
, enough(x)
is False
.
In our binary search, our loop invariant is that enough(hi) = True
. At the beginning, enough(m*n) = True
, and whenever hi
is set, it is set to a value that is "enough" (enough(mi) = True
). That means hi
will be the lowest such value at the end of our binary search.
This leaves us with the task of counting how many values are less than or equal to x
. For each of m
rows, the i
th row looks like [i, 2*i, 3*i, ..., n*i]
. The largest possible k*i <= x
that could appear is k = x // i
. However, if x
is really big, then perhaps k > n
, so in total there are min(k, n) = min(x // i, n)
values in that row that are less than or equal to x
.
After we have the count of how many values in the table are less than or equal to x
, by the definition of enough(x)
, we want to know if that count is greater than or equal to k
.
Python
class Solution(object):
def findKthNumber(self, m, n, k):
def enough(x):
count = 0
for i in xrange(1, m+1):
count += min(x // i, n)
return count >= k
lo, hi = 1, m * n
while lo < hi:
mi = (lo + hi) / 2
if not enough(mi):
lo = mi + 1
else:
hi = mi
return lo
Java
class Solution {
public boolean enough(int x, int m, int n, int k) {
int count = 0;
for (int i = 1; i <= m; i++) {
count += Math.min(x / i, n);
}
return count >= k;
}
public int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mi = lo + (hi  lo) / 2;
if (!enough(mi, m, n, k)) lo = mi + 1;
else hi = mi;
}
return lo;
}
}
Complexity Analysis

Time Complexity: $$O(m * \log (m*n))$$. Our binary search divides the interval
[lo, hi]
into half at each step. At each step, we callenough
which does $$O(m)$$ work. 
Space Complexity: $$O(1)$$. We only keep integers in memory during our intermediate calculations.