LeetCode 668: Kth Smallest Number in Multiplication Table Solution in Python – A Step-by-Step Guide

What Is LeetCode 668: Kth Smallest Number in Multiplication Table?

In LeetCode 668: Kth Smallest Number in Multiplication Table, you’re given three integers: m (rows), n (columns), and k. These define an m × n multiplication table where each cell (i, j) (1-based) contains the product i * j. Your task is to find the kth smallest number in this table, considering all m * n values (including duplicates). Return this number as an integer. For example, with m = 3, n = 3, k = 5, the table is [1, 2, 3, 2, 4, 6, 3, 6, 9], and the 5th smallest number is 4. This problem tests your ability to efficiently find order statistics in a structured but implicit dataset.

Problem Statement

• Input:
• m: Integer (number of rows).
• n: Integer (number of columns).
• k: Integer (kth smallest number to find, 1-based).
• Output: An integer—kth smallest number in the m × n multiplication table.
• Rules:
• Table: m × n grid, cell (i, j) = i * j (1-based).
• Find kth smallest value among all m * n entries.
• Values may have duplicates.

Constraints

• 1 ≤ m, n ≤ 3 * 10⁴.
• 1 ≤ k ≤ m * n.

Examples

• Input: m = 3, n = 3, k = 5
• Output: 4 (Table: [1, 2, 3, 2, 4, 6, 3, 6, 9], 5th = 4)
• Input: m = 2, n = 3, k = 6
• Output: 6 (Table: [1, 2, 3, 2, 4, 6], 6th = 6)
• Input: m = 1, n = 1, k = 1
• Output: 1 (Table: [1], 1st = 1)

These examples set the table—let’s solve it!

Understanding the Problem: Finding the kth Smallest

To solve LeetCode 668: Kth Smallest Number in Multiplication Table in Python, we need to find the kth smallest number in an m × n multiplication table without generating the entire table, which would be O(m * n) space and inefficient for m, n ≤ 3 * 10⁴. A brute-force approach—computing all products, sorting, and picking the kth—would be O(m * n * log(m * n)), too slow. Since the table’s values increase predictably, we can optimize with binary search or a heap. We’ll use:

• Best Solution (Binary Search with Count): O(m log(m n)) time, O(1) space—fast and space-efficient.
• Alternative Solution (Heap-Based Approach): O(k * log k) time, O(k) space—intuitive but slower for large k.

Let’s start with the binary search solution, breaking it down for beginners.

Best Solution: Binary Search with Count

Why This Is the Best Solution

The binary search with count approach is the top choice for LeetCode 668 because it’s highly efficient—O(m * log(m * n)) time with O(1) space—and leverages the table’s sorted nature to binary search over possible values, counting how many numbers are less than or equal to a mid-point to hone in on the kth smallest. It fits constraints (m, n ≤ 3 * 10⁴) perfectly and is elegant once you see the counting trick. It’s like guessing the number and narrowing it down with clever checks!

How It Works

Think of this as a number guesser:

• Step 1: Define Search Range:
• Min value = 1 (1 1), max = m n (largest product).
• Step 2: Binary Search:
• Guess a mid value.
• Count numbers ≤ mid in the table:
• For each row i (1 to m), count = min(n, mid // i).
• If count < k, search higher; else, search lower or equal.
• Step 3: Converge to kth Smallest:
• Left pointer settles on the answer.
• Step 4: Return Result:
• Return left value.

It’s like a value finder—guess and count!

Step-by-Step Example

Example: m = 3, n = 3, k = 5

• Step 1: Range: low = 1, high = 9.
• Step 2: Binary search:
• Mid = 5:
• Row 1: min(3, 5//1) = 3 (1, 2, 3).
• Row 2: min(3, 5//2) = 2 (2, 4).
• Row 3: min(3, 5//3) = 1 (3).
• Count = 3 + 2 + 1 = 6 > k=5, high = 4.
• Mid = 2:
• Row 1: min(3, 2//1) = 2 (1, 2).
• Row 2: min(3, 2//2) = 1 (2).
• Row 3: min(3, 2//3) = 0 (none).
• Count = 2 + 1 + 0 = 3 < k=5, low = 3.
• Mid = 3:
• Row 1: min(3, 3//1) = 3 (1, 2, 3).
• Row 2: min(3, 3//2) = 1 (2).
• Row 3: min(3, 3//3) = 1 (3).
• Count = 3 + 1 + 1 = 5 = k=5, high = 3.
• Mid = 4:
• Row 1: min(3, 4//1) = 3 (1, 2, 3).
• Row 2: min(3, 4//2) = 2 (2, 4).
• Row 3: min(3, 4//3) = 1 (3).
• Count = 3 + 2 + 1 = 6 > k=5, high = 4.
• Step 3: Low = 4 when converged, verify: 5th smallest in [1, 2, 3, 2, 4, 6, 3, 6, 9] is 4.
• Output: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # Step 1: Define search range
        low = 1
        high = m * n

        # Step 2: Binary search for kth smallest
        while low < high:
            mid = (low + high) // 2

            # Count numbers <= mid
            count = 0
            for i in range(1, m + 1):
                count += min(n, mid // i)

            # Adjust range
            if count < k:
                low = mid + 1
            else:
                high = mid

        # Step 3: Return kth smallest
        return low

• Lines 4-6: Init: Range from 1 to m * n.
• Lines 9-19: Binary search:
• Guess mid, count numbers ≤ mid per row, adjust range.
• Line 22: Return low (kth smallest).
• Time Complexity: O(m log(m n))—log(m * n) iterations, O(m) counting.
• Space Complexity: O(1)—no extra space.

This is like a number hunter—search and pinpoint!

Alternative Solution: Heap-Based Approach

Why an Alternative Approach?

The heap-based approach uses a min-heap—O(k * log k) time, O(k) space. It’s more intuitive, building a priority queue of products up to k, but slower for large k and less space-efficient. It’s like collecting the smallest treasures until you have enough!

How It Works

Picture this as a treasure gatherer:

• Step 1: Init heap with first row.
• Step 2: Extract k elements:
• Pop smallest, add next product from same column.
• Step 3: Return kth element.

It’s like a heap collector—gather and pick!

Step-by-Step Example

Example: Same as above

• Step 1: Heap = [(1, 1, 1), (2, 1, 2), (3, 1, 3)].
• Step 2: Extract 5:
• Pop (1, 1, 1), add (2, 2, 1), heap = [(2, 1, 2), (2, 2, 1), (3, 1, 3)].
• Pop (2, 1, 2), add (4, 2, 2), heap = [(2, 2, 1), (3, 1, 3), (4, 2, 2)].
• Pop (2, 2, 1), add (3, 3, 1), heap = [(3, 1, 3), (3, 3, 1), (4, 2, 2)].
• Pop (3, 1, 3), heap = [(3, 3, 1), (4, 2, 2)].
• Pop (3, 3, 1), heap = [(4, 2, 2)], kth = 4.
• Step 3: Return 4.
• Output: 4.

Code for Heap Approach

Copy codeimport heapq

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # Step 1: Initialize min-heap with first row
        heap = [(i, i, 1) for i in range(1, min(n, m) + 1)]  # (value, row, col)
        heapq.heapify(heap)

        # Step 2: Extract k elements
        for _ in range(k):
            val, row, col = heapq.heappop(heap)
            if col < n:
                heapq.heappush(heap, (row * (col + 1), row, col + 1))

        # Step 3: Return kth element
        return val

• Line 1: Import heapq for min-heap.
• Lines 6-7: Init: Heap with first row products.
• Lines 10-13: Extract:
• Pop smallest, add next column product, repeat k times.
• Line 16: Return kth value.
• Time Complexity: O(k * log k)—k extractions.
• Space Complexity: O(k)—heap size.

It’s a treasure picker—heap and extract!

Comparing the Two Solutions

• Binary Search (Best):
• Pros: O(m log(m n)) time, O(1) space, fast for large k.
• Cons: Counting logic less obvious.
• Heap (Alternative):
• Pros: O(k * log k) time, O(k) space, intuitive heap.
• Cons: Slower for large k, more space.

Binary search wins for efficiency.

Additional Examples and Edge Cases

• Input: m = 1, n = 1, k = 1
• Output: 1.
• Input: m = 2, n = 2, k = 4
• Output: 4 (Table: [1, 2, 2, 4]).

Binary search handles these well.

Complexity Breakdown

• Binary Search: Time O(m log(m n)), Space O(1).
• Heap: Time O(k * log k), Space O(k).

Binary search is optimal for large inputs.

Key Takeaways

• Binary Search: Count guessing—smart!
• Heap: Heap collecting—clear!
• Tables: Searching is fun.
• Python Tip: Binary search rocks—see Python Basics.

Final Thoughts: Find That Number

LeetCode 668: Kth Smallest Number in Multiplication Table in Python is a fun search challenge. Binary search with count offers speed and minimal space, while heap-based provides an intuitive alternative. Want more? Try LeetCode 215: Kth Largest Element or LeetCode 378: Kth Smallest Element in a Sorted Matrix. Ready to hunt? Head to Solve LeetCode 668 on LeetCode and find that kth number today!