Kth Smallest Element in a Row-Column Wise Sorted Matrix

Understanding the Problem

The goal is to find the Kth smallest element in a matrix that is sorted row-wise and column-wise.

Method 1: Using a Combined Array

This method combines all elements into a single array and then sorts it.

import java.util.Arrays;

public class KthSmallestElement {
    public static int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] combined = new int[rows * cols];
        int index = 0;

        // Combine all elements into a single array
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                combined[index++] = matrix[i][j];
            }
        }

        // Sort the combined array
        Arrays.sort(combined);

        // Return the Kth smallest element
        return combined[k - 1];
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {10, 20, 30},
            {15, 25, 35},
            {27, 29, 37},
            {32, 33, 38}
        };
        int k = 5;
        System.out.println("Kth smallest element: " + kthSmallest(matrix, k));
    }
}
            

Output:

Kth smallest element: 25

Method 2: Using Min-Heap

This method uses a min-heap to find the Kth smallest element efficiently.

import java.util.PriorityQueue;

public class KthSmallestElement {
    static class Element {
        int value;
        int row;
        int col;

        Element(int value, int row, int col) {
            this.value = value;
            this.row = row;
            this.col = col;
        }
    }

    public static int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);

        // Push the first element of each row into the min-heap
        for (int i = 0; i < rows; i++) {
            minHeap.offer(new Element(matrix[i][0], i, 0));
        }

        Element current = null;
        for (int i = 0; i < k; i++) {
            current = minHeap.poll();

            // If there is a next element in the same row, push it into the heap
            if (current.col + 1 < cols) {
                minHeap.offer(new Element(matrix[current.row][current.col + 1], current.row, current.col + 1));
            }
        }
        return current.value; // The Kth smallest element
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {10, 20, 30},
            {15, 25, 35},
            {27, 29, 37},
            {32, 33, 38}
        };
        int k = 5;
        System.out.println("Kth smallest element: " + kthSmallest(matrix, k));
    }
}
            

Output:

Kth smallest element: 25

Method 3: Using Binary Search

This method uses binary search to find the Kth smallest element.

public class KthSmallestElement {
    public static int countLessEqual(int[][] matrix, int mid) {
        int count = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int row = rows - 1, col = 0;

        while (row >= 0 && col < cols) {
            if (matrix[row][col] <= mid) {
                count += (row + 1); // All elements in this row are <= mid
                col++;
            } else {
                row--;
            }
        }
        return count;
    }

    public static int kthSmallest(int[][] matrix, int k) {
        int low = matrix[0][0], high = matrix[matrix.length - 1][matrix[0].length - 1];

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countLessEqual(matrix, mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low; // The Kth smallest element
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {10, 20, 30},
            {15, 25, 35},
            {27, 29, 37},
            {32, 33, 38}
        };
        int k = 5;
        System.out.println("Kth smallest element: " + kthSmallest(matrix, k));
    }
}

Output:

Kth smallest element: 25