Watch 10 video solutions for Kth Smallest Element in a Sorted Matrix, a medium level problem involving Array, Binary Search, Sorting. This walkthrough by Techdose has 23,161 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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(n2).
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].length1 <= n <= 300-109 <= matrix[i][j] <= 109matrix are guaranteed to be sorted in non-decreasing order.1 <= k <= n2
Follow up:
O(1) memory complexity)?O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.Problem Overview: You are given an n x n matrix where each row and column is sorted in ascending order. The task is to return the kth smallest element in the matrix. Because both rows and columns are sorted, the matrix behaves like multiple sorted lists merged together.
Approach 1: Flatten + Sort (O(n² log n²) time, O(n²) space)
The most direct solution ignores the sorted structure. Iterate through the matrix, push every element into a list, and sort it. After sorting, the element at index k - 1 is the answer. This approach is simple but inefficient because it processes all n² elements even though the matrix already provides ordering guarantees. It’s mainly useful as a baseline or quick prototype using basic array and sorting operations.
Approach 2: Min-Heap (O(k log n) time, O(n) space)
This method treats each row like a sorted list and merges them using a min-heap. Push the first element of every row into the heap along with its row and column index. Repeatedly extract the smallest element from the heap. When an element (r, c) is removed, push the next element in that row (r, c+1) if it exists. After performing k heap extractions, the last popped value is the answer. The heap size never exceeds n, making operations efficient. This technique is a classic application of heap (priority queue) for merging sorted structures.
Approach 3: Binary Search on Value Range (O(n log(max-min)) time, O(1) space)
The optimal solution performs binary search over the value range rather than indices. The smallest possible value is matrix[0][0] and the largest is matrix[n-1][n-1]. For a chosen midpoint, count how many numbers in the matrix are less than or equal to it. Because rows and columns are sorted, this count can be computed in O(n) by starting from the bottom-left corner and moving either up or right. If the count is less than k, move the search range higher; otherwise move it lower. The search converges to the kth smallest value without explicitly storing elements.
Recommended for interviews: The binary search solution is usually what interviewers expect because it leverages the sorted matrix structure and achieves O(n log(max-min)) time with constant extra space. The heap approach is also widely accepted and easier to implement. Mentioning the flatten-and-sort baseline shows understanding of the problem before optimizing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Flatten Matrix + Sort | O(n² log n²) | O(n²) | Simple baseline when constraints are small or quick implementation is needed |
| Min-Heap (Merge Sorted Rows) | O(k log n) | O(n) | Good when k is small relative to n² and you want a straightforward heap solution |
| Binary Search on Value Range | O(n log(max-min)) | O(1) | Best for interviews and large matrices since it uses the sorted row/column property efficiently |