Today's Challenge

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

Kth Smallest Element in a Sorted Matrix - LeetCode

단순히 배열을 합쳐서 정렬하면 끝나는 문제이긴 한데,
n이 커지면 이런 방법으로는 불가함. 그래서 binary search를 이용하면 됨.

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        l, r, n = matrix[0][0], matrix[-1][-1], len(matrix)
        
        def less_k(m):
            cnt = 0
            for r in range(n):
                x = bisect_right(matrix[r], m)
                cnt += x
            return cnt
    
        while l < r:
            mid = (l + r) // 2
            
            if less_k(mid) < k:
                l = mid + 1
            else:
                r = mid
        
        return l