Finding the kth smallest element in a sorted matrix.

Here’s a Java program that finds the kth smallest element in a sorted matrix:

 import java.util.PriorityQueue;

 public class KthSmallestElementInMatrix {

    public static int kthSmallest(int[][] matrix, int k) {

        int n = matrix.length;

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add the first element of each row to the minHeap

        for (int i = 0; i < n; i++) {

            minHeap.offer(matrix[i][0]);

        }

        // Extract the smallest element from the minHeap k-1 times

        for (int i = 0; i < k - 1; i++) {

            int smallest = minHeap.poll();

            int row = smallest / n; // Calculate the row index

            int col = smallest % n; // Calculate the column index

            // If there are more elements in the current row, add the next element to the minHeap

            if (col < n - 1) {

                minHeap.offer(matrix[row][col + 1]);

            }
        }

        // The kth smallest element will be the root of the minHeap

        return minHeap.poll();

    }

    public static void main(String[] args) {

        int[][] matrix = {

            {1, 5, 9},

            {10, 11, 13},

            {12, 13, 15}

        };

        int k = 8;

        int kthSmallestElement = kthSmallest(matrix, k);

        System.out.println("The kth smallest element in the matrix is: " + kthSmallestElement);
    }

}

This program uses a min-heap (PriorityQueue) to keep track of the smallest elements from each row of the matrix. It starts by adding the first element from each row to the minHeap. Then, it extracts the smallest element from the minHeap (k-1) times, considering the column index to determine if there are more elements in the current row. Finally, it returns the kth smallest element, which is the root of the minHeap.

In the provided example, the program finds the 8th smallest element in the matrix, which is 13. You can modify the `matrix` and `k` variables in the `main` method to test the program with different inputs.