K-th Smallest element in a row and column wise sorted matrix

In this article, we have discussed how can we find the kth smallest element in a given n x n matrix, in which every row and column is sorted in non-decreasing order.

Table of contents:

Problem StatementBrute force approachUsing min-heap data structureUsing binary searchProblem statement

Problem statement: Find the kth smallest element in a given n x n matrix, in which every row and column is sorted in non-decreasing order.

Example:

K=3, matrix:
15, 25, 31, 43
16, 27, 36, 45
28, 30, 39, 49...