Leetcode 378. Kth Smallest Element in a Sorted Matrix
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
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
Input: matrix = [[-5]], k = 1
n == matrix.length == matrix[i].length
1 <= n <= 300
-10^9 <= matrix[i][j] <= 10^9
- All the rows and columns of
matrixare guaranteed to be sorted in non-decreasing order.
1 <= k <= n^2
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.
- 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).