Blind 75 - problem 13 : Find Kth Smallest Element in a Sorted Matrix

Problem Statement:

Find Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, find the kth smallest element in the matrix.

Implement the function:

int kthSmallest(vector<vector<int>>& matrix, int k);

Optimal Approach:

The most efficient way to solve this problem is by using a min-heap (priority queue) to efficiently extract the smallest elements. We can use the heap to store the first element of each row, and then extract the smallest element, moving the next element of the corresponding row into the heap. This approach operates in O(k log n) time, where n is the number of rows (or columns) and k is the position of the smallest element we are interested in.

Steps:

1. Initialize a min-heap and insert the first element of each row along with its row and column index.
2. Pop the smallest element from the heap, then push the next element from the same row into the heap.
3. Repeat this until the kth element is popped from the heap.

LeetCode-Compatible Code Implementation:

#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        auto comp = [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
            return get<0>(a) > get<0>(b); // min-heap based on the value of elements
        };
        
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(comp)> minHeap(comp);
        
        // Initialize heap with the first element of each row
        for (int i = 0; i < n; i++) {
            minHeap.push({matrix[i][0], i, 0}); // {value, row, column}
        }

        // Extract the minimum element from the heap k times
        for (int i = 1; i < k; i++) {
            auto [val, row, col] = minHeap.top();
            minHeap.pop();
            
            // If there is another element in the same row, push it into the heap
            if (col + 1 < n) {
                minHeap.push({matrix[row][col + 1], row, col + 1});
            }
        }

        return minHeap.top().get<0>(); // The kth smallest element
    }
};

Step-by-Step Explanation of Code:

1. Define a priority queue (min-heap):

   • The heap stores tuples containing the value of the element, row, and column index of the element. We define a custom comparator to ensure the smallest element is at the top.

2. Initialize the heap:

   • Insert the first element of each row into the heap. Each tuple in the heap will have the structure {value, row, column}.

3. Process the heap:

   • For k-1 iterations, extract the smallest element from the heap.
   • If the extracted element's column has a next element in the same row, insert it into the heap.

4. Return the kth smallest element:

   • After the kth extraction, the top of the heap contains the kth smallest element.

Dry Run / Execution Steps:

Let’s dry-run the algorithm with the sample input.

Input:

matrix = [
  [1, 5, 9],
  [10, 11, 13],
  [12, 13, 15]
]
k = 8

Step-by-Step Execution:

1. Initialize the heap with the first element of each row:

   minHeap = [(1, 0, 0), (10, 1, 0), (12, 2, 0)]
   

2. Pop the smallest element (1), and push the next element from row 0:

   minHeap = [(5, 0, 1), (10, 1, 0), (12, 2, 0)]
   

3. Pop the smallest element (5), and push the next element from row 0:

   minHeap = [(9, 0, 2), (10, 1, 0), (12, 2, 0)]
   

4. Pop the smallest element (9), and push the next element from row 1:

   minHeap = [(10, 1, 0), (12, 2, 0), (11, 1, 1)]
   

5. Continue this process until we reach the 8th element:

   • After popping the smallest elements and inserting the next ones, the 8th smallest element is 13.

Output:

Output = 13

Alternative Approaches & Why Not?

1. Brute Force: Flatten the matrix into a 1D array and sort it. This would take O(n^2 log(n^2)) time, which is less efficient than the heap approach.
2. Binary Search: You could use binary search on the values, but this would require additional handling for counting elements, and the complexity could still be higher in practice than using a heap.

Best Solution & Why It’s Best:

The min-heap approach is the most efficient. It allows us to extract the smallest element k times with a time complexity of O(k log n), making it optimal. It’s better than sorting because sorting would take O(n^2 log(n)) time.

Approach	Time Complexity	Space Complexity
Brute Force	O(n^2 log(n^2))	O(n^2)
Sorting	O(n^2 log(n^2))	O(n^2)
Min-Heap	O(k log n)	O(n)

Complexity Analysis:

• Time Complexity:

  • Brute Force: O(n^2 log(n^2))
  • Sorting: O(n^2 log(n^2))
  • Min-Heap: O(k log n)

• Space Complexity:

  • Brute Force: O(n^2)
  • Sorting: O(n^2)
  • Min-Heap: O(n)

Conclusion:

The min-heap approach is the most efficient for finding the kth smallest element in a sorted matrix. For practice, you can try problems like:

• Kth Smallest Element in a Sorted Matrix
• Merge k Sorted Lists