Kth Smallest Number in Multiplication Table | LeetCode | Solution Explained

668. Kth Smallest Number in Multiplication Table. I explain the binary search approach in detail along with visuals to help things. LeetCode Problem Link.

0. Kth Smallest Number in Multiplication Table: Problem Discussion

0.0. IO Format

• Given: M, N (#rows & #cols)
• Grid structure: matrix[i][j] = (i+1) * (j+1)
• Goal: Find the kth smallest number

0.1. Bruteforce Solution

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        mat = []
        for i in range(m):
            for j in range(n):
                mat.append((i+1)*(j+1))
        
        mat.sort()
        print(mat)
        return mat[k-1]

Complexity Analysis:

• Time: O(MNlogMN) for sorting
• Space: O(MNlogMN) for sorting

1. Kth Smallest Number in Multiplication Table: Observations & Logic

1.0. Intuitions

My first instincts were to find some sort of pattern hidden underneath the grid. Some layout of numbers.

This approach did not work, but it does give a sense of how numbers work.

When it comes to a non-symmetric grid layout, things become a lot more challenging.

Clearly, this approach will not work too well.

1.1. A Change in Perspective

We saw how in the bruteforce solution, we first sorted the array, then, accessing the kth element of the matrix gave us the answer.

What if … we flip the problem on its own head?

What if instead of focusing on the kth index, we try to find the number that happens to be the kth index?

Let me explain.

Our goal is to find the kth element, this element has some numbers lesser than or equals to the answer (present on the left) and some present on the right. Imagine it as a sorted array kind of structure. We don’t sort, we just imagine it as such.

1.2. Examples

In the grid below, can we answer how many numbers are less than or equals to 5?

Again, we could iterate over all the numbers in the matrix. But, what if we do some observations first?

Let’s recolor the elements <= target (5 in this case).

What do we observe? Well the colored part looks symmetric, but also, if we know the current row we are at, say i and the total number of columns, N, we can find the solution easily. Its just target//i!

Why? The ith row looks something of the sort: i 2i 3i 4i ... Ni.

To know which elements are <= target, we can just divide 🙂

In this case, for the row say #2, target//i = 5//2 = 2. And that is what we see!

As a quick note, its not always going to be target//i, we have to also account for a case like i = 2, N = 5 but target = 100.

Thus, #numbers <= target =sum(min(target//i, n) for i in range(1, m+1))

1.3. What now?

Let’s say that the k given is 6. What can we say about the target = 5? We find that the #numbers <= 5 is 10. This overshoots. So, we definitely know that target = 6 will also overshoot from the k!

This means we have to look for smaller values. So, what about 3? #numbers <= 3 is 5. This undershoots. This means that now we have to look for larger values again (not values >=5 though, those are way too high!)

Finally, we come onto the number 4. #number <= 4 is 7. That is still higher.

But wait!

target = 3: too low

target = 4: too high

target = 5: too high

So, what could the answer be? 4! Because we know 3 is too low, we go to 4. It is OK if #numbers <= 4 is higher than expected – after all, there can be many 4s 😀

Thus, the condition can read:

if #numbers < k: higher the lo, the target is inadequate

else: lower the hi

2. Kth Smallest Number in Multiplication Table: Implementation

2.0. Code

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def f(target):
            return sum(min(target//i, n) for i in range(1, m+1))
        
        
        lo, hi = 0, (m+1)*(n+1)
        
        while lo < hi:
            mid = (lo + hi) // 2
            if f(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        
        return lo

2.1. Complexity Analysis

• Time: O(Mlog(MN)). O(log(MN)) for the binary search and O(M) for each request to the function f to return the #numbers <= target.
• Space: O(1). We don’t store anything other than a few simple variables.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.