# Leetcode 378. Kth Smallest Element in a Sorted Matrix

# 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 = 8

**Output:** 13

**Explanation:** 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 = 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`

# 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

- Create a maxHeap.
- Traverse through the matrix and keep on adding elements to the maxHeap.
- If the size of the maxHeap becomes greater than k, just poll the topmost element and continue traversing.
- 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).**