Kth Smallest Element in a Sorted Matrix
Problem Description
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].length
- 1 <= n <= 300
- -109 <= matrix[i][j] <= 109
- All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
- 1 <= k <= n2
Follow up:
- Could you solve the problem with a constant memory (i.e.,
O(1)memory complexity)? - Could you solve the problem in
O(n)time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.
Solve it on LeetCode
Approaches
1. Brute Force with Sorting
Intuition:
The simplest approach to solve this problem is by extracting all the elements from the matrix and placing them into a list. Once we have a list, we can sort it and then directly access the kth smallest element from this sorted list.
Algorithm:
- Create a list to store all elements of the matrix.
- Traverse the matrix and add each element to the list.
- Sort the list.
- Return the element at the kth index in the sorted list.
Code:
- Time Complexity: O(n^2 * log n) for sorting the list that contains all matrix elements.
- Space Complexity: O(n^2) for storing all elements from the matrix.
2. Min-Heap
Intuition:
To improve upon the brute force sorting solution, we can make use of a min-heap. The idea is to store each element in a min-heap so that we can extract the smallest element efficiently. Since the matrix rows (and columns) are sorted, we start placing elements into the heap one row at a time.
We maintain the heap for at most the size of the matrix's row by column, extract the smallest element from the heap k times, which will give us the kth smallest element.
Algorithm:
- Create a min-heap and add the first element of each row (along with row and column indices).
- Extract the smallest element from the heap k times.
- For each extraction, if the extracted element's column has another element in the row, add it to the heap.
- The kth extracted element is our answer.
Code:
- Time Complexity: O(klog n) because each insertion and extraction from the heap takes O(log n) and we perform the extraction k times.
- Space Complexity: O(n) because we store up to n elements in the heap.
3. Binary Search
Intuition:
The row and column sorted property of the matrix allows us to use binary search. We search within the range of the smallest and largest element of the matrix. For each midpoint value, count how many elements are less than or equal to it. Adjust the search range based on this count relative to k.
Algorithm:
- Initialize two pointers:
leftto the smallest element andrightto the largest element in the matrix. - Perform binary search:
- Find the midpoint between
leftandright. - Count elements less than or equal to the midpoint.
- If this count is less than k, move
leftup; otherwise, moverightdown. - Once the search is complete,
leftcontains the kth smallest element.
Code:
- Time Complexity: O(n * log (max - min)) where log(max - min) relates to binary search range, and n to count elements.
- Space Complexity: O(1) as we're not using extra space beyond variables.