Leetcode 378. Kth Smallest Element in a Sorted Matrix

Accepted Code

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

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).

Code

Java Code

LeetCodeTopInterviewQuestions/02_Kth_Smallest_Element_In_A_Sorted_Matrix.java at master ·…