Day 84 of 100 days dsa coding challenge

Source: Dev.to

Problem

GeeksforGeeks – Kth smallest element in a Matrix

Difficulty: Medium | Accuracy: 61.42%

Given a matrix mat[][] of size n × n, where each row and column is sorted in non‑decreasing order, find the k‑th smallest element in the matrix.

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