100일 DSA 코딩 챌린지 Day 84

Source: Dev.to

Problem

GeeksforGeeks – Kth smallest element in a Matrix

Difficulty: Medium | Accuracy: 61.42%

주어진 mat[][] 행렬은 크기가 n × n이며, 각 행과 각 열이 비내림차순으로 정렬되어 있습니다. 행렬에서 k번째로 작은 원소를 찾아라.

Solution

class Solution:
    def kthSmallest(self, mat, k):
        n = len(mat)
        low, high = mat[0][0], mat[-1][-1]

        while low < high:
            mid = (low + high) // 2
            count = 0

            # Count elements ≤ mid in each row using binary search
            for row in mat:
                l, r = 0, n
                while l < r:
                    m = (l + r) // 2
                    if row[m] <= mid:
                        l = m + 1
                    else:
                        r = m
                count += l

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

        return low