# Problem Statement

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

Note that it is the `kth` smallest element in the sorted order, not the `kth` distinct element.

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

# Test Cases

Example 1:

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

Example 2:

`Input: matrix = [[-5]], k = 1Output: -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`

# Approach

This is another variation of finding kth largest/smallest number from a given input. A small change is that the input is a matrix. Anyway, we can still continue with our general approach of finding kth largest/smallest number using priorityqueue/heap.

Since this is finding the kth smallest element in the matrix, we will be using a maxHeap and if the question was the kth largest element in the matrix, then it will be minHeap.

## Algorithm

1. Create a maxHeap.
2. Traverse through the matrix and keep on adding elements to the maxHeap.
3. If the size of the maxHeap becomes greater than k, just poll the topmost element and continue traversing.
4. Finally return whatever element present at the top of the heap.

# Time and Space Complexity

We are using a priority queue that sorts the element being added into the heap + we are also traversing through the matrix. So the time complexity will be O(n*nlog(n*n)) + O(n² * log(n²)) as logn time will be taken for adding an element to the heap.

Maximum K elements will be stored inside the maxheap, so our space complexity will be O(K).