Kth Smallest Element in a Sorted Matrix

Given a square matrix matrix, where each row and column is sorted in non-decreasing order, find the kth smallest element in the matrix.

Note: It is guaranteed that k is less than or equal to the number of elements in the matrix.

Sample Input/Output:

Sample input:

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

Expected Output:

13

Explanation:
For the given input matrix, the sorted matrix will be:

[ 1,  5,  9]
[10, 11, 13]
[12, 13, 15]

The 8th smallest element in the sorted matrix is 13.

Time and Space Complexity:

The time complexity of the solution will be O(k log N), where N is the side length of the square matrix. We perform at most k binary searches, and each search takes log N time.

The space complexity will be O(N) to store the elements of the matrix in a min-heap.

Now, let’s implement the solution in C++:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Add the first column elements to the min-heap
    for (int i = 0; i < n; ++i) {
        minHeap.push(matrix[i][0]);
    }

    // Perform k-1 extractions to get the kth smallest element
    for (int i = 0; i < k - 1; ++i) {
        int smallest = minHeap.top();
        minHeap.pop();

        // Move to the next element in the same row and add it to the min-heap
        for (int j = 1; j < n; ++j) {
            if (matrix[j].size() > i + 1) {
                minHeap.push(matrix[j][i + 1]);
            }
        }
    }

    return minHeap.top();
}

int main() {
    vector<vector<int>> matrix = {
        {1, 5, 9},
        {10, 11, 13},
        {12, 13, 15}
    };
    int k = 8;

    int result = kthSmallest(matrix, k);

    cout << "The " << k << "th smallest element is: " << result << endl;

    return 0;
}

In this implementation, we use a min-heap to find the kth smallest element in the sorted matrix. We start by adding the elements from the first column of the matrix to the min-heap. Then, we perform k-1 extractions from the heap, where in each iteration, we extract the smallest element, move to the next element in the same row, and add it to the min-heap. We repeat this process k-1 times to get the kth smallest element.

The main function demonstrates the usage of kthSmallest by finding the 8th smallest element in the given matrix.

The output for the provided test case will be:

The 8th smallest element is: 13