# Kth Smallest Element In A Sorted Matrix Problem

## Description

LeetCode Problem 378.

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k^th smallest element in the matrix.

Note that it is the k^th smallest element in the sorted order, not the k^th distinct element.

You must find a solution with a memory complexity better than O(n^2).

Example 1:

 1 2 3 Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8^th smallest number is 13

Example 2:

 1 2 Input: matrix = [[-5]], k = 1 Output: -5

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n^2

## Sample C++ Code

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public: int kthSmallest(vector>& matrix, int k) { int n = matrix.size(); int left = matrix[0][0], right = matrix[n-1][n-1]; int mid; while (left < right) { mid = (left + right) / 2; int lessthanmid = 0; int i = n-1, j = 0; while (i >= 0 && j < n) { if (matrix[i][j] <= mid) { j ++; lessthanmid += i+1; } else { i --; } } if (lessthanmid < k) { left = mid + 1; } else { right = mid; } } return left; } };