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.

#include <iostream>
#include <algorithm>
using namespace std;

int kthSmallest(int matrix[][100], int rows, int cols, int k) {
    int totalElements = rows * cols;
    int combined[totalElements];
    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
    sort(combined, combined + totalElements);

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

int main() {
    int matrix[100][100] = {
        {10, 20, 30},
        {15, 25, 35},
        {27, 29, 37},
        {32, 33, 38}
    };
    int rows = 4, cols = 3, k = 5;
    cout << "Kth smallest element: " << kthSmallest(matrix, rows, cols, k) << endl;
    return 0;
}
            

Output:

Kth smallest element: 25

Method 2: Using Min-Heap

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

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

struct Element {
    int value;
    int row;
    int col;
};

struct Compare {
    bool operator()(Element const &a, Element const &b) {
        return a.value > b.value; // Min-heap
    }
};

int kthSmallest(int matrix[][100], int rows, int cols, int k) {
    priority_queue, Compare> minHeap;

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

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

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

int main() {
    int matrix[100][100] = {
        {10, 20, 30},
        {15, 25, 35},
        {27, 29, 37},
        {32, 33, 38}
    };
    int rows = 4, cols = 3, k = 5;
    cout << "Kth smallest element: " << kthSmallest(matrix, rows, cols, k) << endl;
    return 0;
}
            

Output:

Kth smallest element: 25

Method 3: Using Binary Search

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

#include <iostream>
using namespace std;

int countLessEqual(int matrix[][100], int rows, int cols, int mid) {
    int count = 0, 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;
}

int kthSmallest(int matrix[][100], int rows, int cols, int k) {
    int low = matrix[0][0], high = matrix[rows - 1][cols - 1];

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

int main() {
    int matrix[100][100] = {
        {10, 20, 30},
        {15, 25, 35},
        {27, 29, 37},
        {32, 33, 38}
    };
    int rows = 4, cols = 3, k = 5;
    cout << "Kth smallest element: " << kthSmallest(matrix, rows, cols, k) << endl;
    return 0;
}
            

Output:

Kth smallest element: 25