Skip to content

Binary Search Kth Min Max

Table of Contents

668. Kth Smallest Number in Multiplication Table

378. Kth Smallest Element in a Sorted Matrix

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, sorting, heap priority queue, matrix

  • Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the k-th smallest element in the matrix.
378. Kth Smallest Element in a Sorted Matrix - Python Solution
from heapq import heapify, heappop, heappush
from typing import List


# Heap - Merge K Sorted
def kthSmallestHeap(matrix: List[List[int]], k: int) -> int:
    n = len(matrix)
    heap = [(matrix[i][0], i, 0) for i in range(n)]
    heapify(heap)

    for _ in range(k - 1):
        _, row, col = heappop(heap)

        if col + 1 < n:
            heappush(heap, (matrix[row][col + 1], row, col + 1))

    return heappop(heap)[0]


# Binary Search
def kthSmallestBinarySearch(matrix: List[List[int]], k: int) -> int:
    n = len(matrix)

    def check(mid):
        i, j = n - 1, 0
        num = 0

        while i >= 0 and j < n:
            if matrix[i][j] <= mid:
                num += i + 1
                j += 1
            else:
                i -= 1

        return num >= k

    left, right = matrix[0][0], matrix[-1][-1]

    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1

    return left


matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
k = 8

print(kthSmallestHeap(matrix, k))  # 13
print(kthSmallestBinarySearch(matrix, k))  # 13

719. Find K-th Smallest Pair Distance

878. Nth Magical Number

1201. Ugly Number III

793. Preimage Size of Factorial Zeroes Function

373. Find K Pairs with Smallest Sums

373. Find K Pairs with Smallest Sums - Python Solution
import heapq
from typing import List


# Heap - Merge K Sorted
def kSmallestPairs(
    nums1: List[int], nums2: List[int], k: int
) -> List[List[int]]:
    if not nums1 or not nums2 or k <= 0:
        return []

    result = []
    min_heap = []

    for j in range(min(k, len(nums2))):
        heapq.heappush(min_heap, (nums1[0] + nums2[j], 0, j))

    while k > 0 and min_heap:
        _, i, j = heapq.heappop(min_heap)
        result.append([nums1[i], nums2[j]])
        k -= 1

        if i + 1 < len(nums1):
            heapq.heappush(min_heap, (nums1[i + 1] + nums2[j], i + 1, j))

    return result


nums1 = [1, 2, 4, 5, 6]
nums2 = [3, 5, 7, 9]
k = 3
print(kSmallestPairs(nums1, nums2, k))
# [[1, 3], [2, 3], [1, 5]]

1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

786. K-th Smallest Prime Fraction

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, two pointers, binary search, sorting, heap priority queue

786. K-th Smallest Prime Fraction - Python Solution
import heapq
from typing import List


def kthSmallestPrimeFraction(arr: List[int], k: int) -> List[int]:
    max_heap = []

    for j in range(1, len(arr)):
        for i in range(j):
            heapq.heappush(max_heap, (-arr[i] / arr[j], arr[i], arr[j]))

            if len(max_heap) > k:
                heapq.heappop(max_heap)

    return [max_heap[0][1], max_heap[0][2]]


arr = [1, 2, 3, 5]
k = 3
print(kthSmallestPrimeFraction(arr, k))  # [2, 5]

3116. Kth Smallest Amount With Single Denomination Combination

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, binary search, bit manipulation, combinatorics, number theory

3134. Find the Median of the Uniqueness Array

2040. Kth Smallest Product of Two Sorted Arrays

2386. Find the K-Sum of an Array

1508. Range Sum of Sorted Subarray Sums

1918. Kth Smallest Subarray Sum

Comments