Kth smallest element in a row-wise and column-wise sorted 2D array

Given an n x n matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the given 2D array.

Example,

Input:k = 3 and array =
        10, 20, 30, 40
        15, 25, 35, 45
        24, 29, 37, 48
        32, 33, 39, 50 
Output: 20
Explanation: The 3rd smallest element is 20 
Input:k = 7 and array =
        10, 20, 30, 40
        15, 25, 35, 45
        24, 29, 37, 48
        32, 33, 39, 50 
Output: 30
Explanation: The 7th smallest element is 30

BRUTE METHOD:

Intuition:

We create a PriorityQueue<Integer> to store all the elements of the matrix.

Then we traverse through the the priority queue and if k elements are popped out, then we return the element.

As by default min heap is implemented by PriorityQueue.

Implementation:

C++

#include <iostream>
#include <queue>
using namespace std;
 
int kthSmallest(int arr[][4], int n, int k)
{
    // Create a min-heap (priority queue) to store elements
    // in sorted order
    priority_queue<int, vector<int>, greater<int> > pq;
 
    // Add all elements of the 2D array to the min-heap
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pq.push(arr[i][j]);
        }
    }
 
    int c = 0;
    while (!pq.empty()) {
        int temp = pq.top();
        pq.pop();
        c++;
 
        if (c == k)
            return temp;
    }
 
    // If kth smallest element not found, return -1
    return -1;
}
 
int main()
{
    int mat[4][4] = { { 10, 20, 30, 40 },
                      { 15, 25, 35, 45 },
                      { 25, 29, 37, 48 },
                      { 32, 33, 39, 50 } };
 
    int res = kthSmallest(mat, 4, 7);
 
    cout << "7th smallest element is " << res << endl;
 
    return 0;
}

Java

// Java program for kth largest element in a 2d
// array sorted row-wise and column-wise
 
import java.io.*;
import java.util.*;
 
class GFG {
    public static int kthSmallest(int[][] arr, int n, int k)
    {
        // code here.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pq.add(arr[i][j]);
            }
        }
 
        int c = 0;
        while (!pq.isEmpty()) {
            int temp = pq.poll();
            c++;
 
            if (c == k)
                return temp;
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int mat[][] = { { 10, 20, 30, 40 },
                        { 15, 25, 35, 45 },
                        { 25, 29, 37, 48 },
                        { 32, 33, 39, 50 } };
 
        int res = kthSmallest(mat, 4, 7);
 
        System.out.print("7th smallest element is " + res);
    }
}
// This code is contributed by Raunak Singh

Python3

# python program for kth largest element in a 2d
# array sorted row-wise and column-wise
import heapq
 
def kthSmallest(arr, n, k):
    pq = []
    for i in range(n):
        for j in range(n):
            heapq.heappush(pq, arr[i][j])
    c = 0
    while pq:
        temp = heapq.heappop(pq)
        c += 1
        if c == k:
            return temp
    return -1
if __name__ == "__main__":
    mat = [
        [10, 20, 30, 40],
        [15, 25, 35, 45],
        [25, 29, 37, 48],
        [32, 33, 39, 50]
    ]
    res = kthSmallest(mat, 4, 7)
    print("7th smallest element is", res)

C#

using System;
using System.Collections.Generic;
 
class Program {
    static int KthSmallest(int[, ] arr, int n, int k)
    {
        // Create a min-heap (priority queue) to store
        // elements in sorted order
        PriorityQueue<int> pq = new PriorityQueue<int>();
 
        // Add all elements of the 2D array to the min-heap
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pq.Push(arr[i, j]);
            }
        }
 
        int c = 0;
        while (!pq.IsEmpty()) {
            int temp = pq.Pop();
            c++;
 
            if (c == k)
                return temp;
        }
 
        // If kth smallest element not found, return -1
        return -1;
    }
 
    static void Main()
    {
        int[, ] mat = { { 10, 20, 30, 40 },
                        { 15, 25, 35, 45 },
                        { 25, 29, 37, 48 },
                        { 32, 33, 39, 50 } };
 
        int res = KthSmallest(mat, 4, 7);
 
        Console.WriteLine("7th smallest element is " + res);
    }
}
 
// PriorityQueue implementation in C#
class PriorityQueue<T> where T : IComparable<T> {
    private List<T> heap;
 
    public PriorityQueue() { heap = new List<T>(); }
 
    public void Push(T value)
    {
        heap.Add(value);
        int currentIndex = heap.Count - 1;
 
        while (currentIndex > 0) {
            int parentIndex = (currentIndex - 1) / 2;
            if (heap[currentIndex].CompareTo(
                    heap[parentIndex])
                >= 0)
                break;
 
            Swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
        }
    }
 
    public T Pop()
    {
        int lastIndex = heap.Count - 1;
        T minValue = heap[0];
 
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
 
        int currentIndex = 0;
        lastIndex--;
 
        while (true) {
            int leftChildIndex = currentIndex * 2 + 1;
            int rightChildIndex = currentIndex * 2 + 2;
 
            if (leftChildIndex > lastIndex)
                break;
 
            int smallerChildIndex = leftChildIndex;
 
            if (rightChildIndex <= lastIndex
                && heap[rightChildIndex].CompareTo(
                       heap[leftChildIndex])
                       < 0) {
                smallerChildIndex = rightChildIndex;
            }
 
            if (heap[currentIndex].CompareTo(
                    heap[smallerChildIndex])
                <= 0)
                break;
 
            Swap(currentIndex, smallerChildIndex);
            currentIndex = smallerChildIndex;
        }
 
        return minValue;
    }
 
    public bool IsEmpty() { return heap.Count == 0; }
 
    private void Swap(int i, int j)
    {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

Javascript

// Function to find the kth smallest element in a 2D array using a min-heap
function kthSmallest(arr, n, k) {
    // Create a min-heap (priority queue) to store elements in sorted order
    const pq = new PriorityQueue();
 
    // Add all elements of the 2D array to the min-heap
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            pq.enqueue(arr[i][j]);
        }
    }
 
    let c = 0; // Counter to keep track of the smallest elements encountered
    let result = -1; // Initialize the result as -1
 
    // Process elements from the min-heap until the kth smallest is found
    while (!pq.isEmpty()) {
        const temp = pq.dequeue();
        c++;
 
        // Check if we've found the kth smallest element
        if (c === k) {
            result = temp;
            break;
        }
    }
 
    // If kth smallest element not found, result will still be -1
    return result;
}
 
// Priority Queue implementation (min-heap)
class PriorityQueue {
    constructor() {
        this.heap = [];
    }
 
    // Enqueue (insert) an element into the priority queue
    enqueue(val) {
        this.heap.push(val);
        this.bubbleUp(); // Ensure the heap property is maintained
    }
 
    // Dequeue (remove) the smallest element from the priority queue
    dequeue() {
        if (this.isEmpty()) return undefined;
        if (this.heap.length === 1) return this.heap.pop();
 
        const min = this.heap[0]; // The smallest element is at the root
        const end = this.heap.pop(); // Remove the last element
        this.heap[0] = end; // Move the last element to the root
        this.sinkDown(); // Ensure the heap property is maintained
        return min;
    }
 
    // Check if the priority queue is empty
    isEmpty() {
        return this.heap.length === 0;
    }
 
    // Restore the heap property by moving elements up the heap
    bubbleUp() {
        let idx = this.heap.length - 1;
        const element = this.heap[idx];
 
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            const parent = this.heap[parentIdx];
 
            if (element >= parent) break;
 
            this.heap[parentIdx] = element;
            this.heap[idx] = parent;
            idx = parentIdx;
        }
    }
 
    // Restore the heap property by moving elements down the heap
    sinkDown() {
        let idx = 0;
        const length = this.heap.length;
        const element = this.heap[0];
 
        while (true) {
            const leftChildIdx = 2 * idx + 1;
            const rightChildIdx = 2 * idx + 2;
            let leftChild, rightChild;
            let swap = null;
 
            if (leftChildIdx < length) {
                leftChild = this.heap[leftChildIdx];
                if (leftChild < element) {
                    swap = leftChildIdx;
                }
            }
 
            if (rightChildIdx < length) {
                rightChild = this.heap[rightChildIdx];
                if (
                    (swap === null && rightChild < element) ||
                    (swap !== null && rightChild < leftChild)
                ) {
                    swap = rightChildIdx;
                }
            }
 
            if (swap === null) break;
 
            this.heap[idx] = this.heap[swap];
            this.heap[swap] = element;
            idx = swap;
        }
    }
}
 
// Driver code
const mat = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [25, 29, 37, 48],
    [32, 33, 39, 50],
];
 
const k = 7; // Specify the value of k for the kth smallest element
const res = kthSmallest(mat, 4, k);
console.log(`The ${k}th smallest element is ${res}`);

Output

7th smallest element is 30

Time Complexity: O(N^2* log(N^2)); since insertion in priority queue takes log N time and we have inserted N^2 elements.

Space Complexity: O(N^2)

Approach: So the idea is to find the kth minimum element. Each row and each column is sorted. So it can be thought as C sorted lists and the lists have to be merged into a single list, the kth element of the list has to be found out. So the approach is similar, the only difference is when the kth element is found the loop ends.
Algorithm:

The idea is to use min heap. Create a Min-Heap to store the elements
Traverse the first row from start to end and build a min heap of elements from first row. A heap entry also stores row number and column number.
Now Run a loop k times to extract min element from heap in each iteration
Get minimum element (or root) from Min-Heap.
Find row number and column number of the minimum element.
Replace root with the next element from same column and min-heapify the root.
Print the last extracted element, which is the kth minimum element

Implementation:

C++

// kth largest element in a 2d array sorted row-wise and
// column-wise
#include <bits/stdc++.h>
using namespace std;
 
// A structure to store entry of heap. The entry contains
// value from 2D array, row and column numbers of the value
struct HeapNode {
    int val; // value to be stored
    int r; // Row number of value in 2D array
    int c; // Column number of value in 2D array
};
 
// A utility function to minheapify the node harr[i] of a
// heap stored in harr[]
void minHeapify(HeapNode harr[], int i, int heap_size)
{
    int l = i * 2 + 1;
    int r = i * 2 + 2;
     if(l < heap_size&& r<heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){
            HeapNode temp=harr[r];
            harr[r]=harr[i];
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
            minHeapify(harr ,r,heap_size);
        }
          if (l < heap_size && harr[l].val < harr[i].val){
            HeapNode temp=harr[i];            
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
        }
}
 
// This function returns kth
// smallest element in a 2D array
// mat[][]
int kthSmallest(int mat[4][4], int n, int k)
{
    // k must be greater than 0 and smaller than n*n
    if (k < 0 || k >= n * n)
        return INT_MAX;
 
    // Create a min heap of elements from first row of 2D
    // array
    HeapNode harr[n];
    for (int i = 0; i < n; i++)
        harr[i] = { mat[0][i], 0, i };
 
    HeapNode hr;
    for (int i = 0; i < k; i++) {
        // Get current heap root
        hr = harr[0];
 
        // Get next value from column of root's value. If
        // the value stored at root was last value in its
        // column, then assign INFINITE as next value
        int nextval = (hr.r < (n - 1)) ? mat[hr.r + 1][hr.c]: INT_MAX;
 
        // Update heap root with next value
        harr[0] = { nextval, (hr.r) + 1, hr.c };
 
        // Heapify root
        minHeapify(harr, 0, n);
    }
 
    // Return the value at last extracted root
    return hr.val;
}
 
// driver program to test above function
int main()
{
    int mat[4][4] = {
        { 10, 20, 30, 40 },
        { 15, 25, 35, 45 },
        { 25, 29, 37, 48 },
        { 32, 33, 39, 50 },
    };
    cout << "7th smallest element is "
        << kthSmallest(mat, 4, 7);
    return 0;
}
 
// this code is contributed by Rishabh Chauhan

Java

// Java program for kth largest element in a 2d 
// array sorted row-wise and column-wise 
import java.io.*;
 
public class GFG{
     
// A structure to store entry of heap.
// The entry contains value from 2D array,
// row and column numbers of the value 
static class HeapNode
{
     
    // Value to be stored 
    int val;
     
    // Row number of value in 2D array 
    int r;
     
    // Column number of value in 2D array 
    int c;
     
    HeapNode(int val, int r, int c)
    {
        this.val = val;
        this.c = c;
        this.r = r;
    }
}
 
// A utility function to minheapify the node
// harr[i] of a heap stored in harr[] 
static void minHeapify(HeapNode harr[], 
                       int i, int heap_size)
{
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int min = i;
     
    if(l < heap_size&& r<heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){
            HeapNode temp=harr[r];
            harr[r]=harr[i];
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
            minHeapify(harr ,r,heap_size);
        }
          if (l < heap_size && harr[l].val < harr[i].val){
            HeapNode temp=harr[i];            
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
        }
}
 
// This function returns kth smallest
// element in a 2D array mat[][] 
public static int kthSmallest(int[][] mat,int n, int k)
{
     
    // k must be greater than 0 and 
    // smaller than n*n 
    if (k < 0 && k >= n * n)
        return Integer.MAX_VALUE;
     
    // Create a min heap of elements 
    // from first row of 2D array 
    HeapNode harr[] = new HeapNode[n];
     
    for(int i = 0; i < n; i++)
    {
        harr[i] = new HeapNode(mat[0][i], 0, i);
    }
     
    HeapNode hr = new HeapNode(0, 0, 0);
     
    for(int i = 1; i <= k; i++)
    {
         
        // Get current heap root 
        hr = harr[0];
         
        // Get next value from column of root's
        // value. If the value stored at root was
        // last value in its column, then assign
        // INFINITE as next value 
        int nextVal = hr.r < n - 1 ? 
                      mat[hr.r + 1][hr.c] :
                      Integer.MAX_VALUE;
                       
        // Update heap root with next value 
        harr[0] = new HeapNode(nextVal, 
                               hr.r + 1, hr.c);
                                
        // Heapify root 
        minHeapify(harr, 0, n);
    }
     
    // Return the value at last extracted root 
    return hr.val;
}
 
// Driver code
public static void main(String args[])
{
    int mat[][] = { { 10, 20, 30, 40 },
                    { 15, 25, 35, 45 },
                    { 25, 29, 37, 48 },
                    { 32, 33, 39, 50 } };
                     
    int res = kthSmallest(mat, 4, 7);
     
    System.out.print("7th smallest element is "+ res);
}
}
 
// This code is contributed by Rishabh Chauhan

Python3

# Program for kth largest element in a 2d array 
# sorted row-wise and column-wise 
from sys import maxsize 
 
# A structure to store an entry of heap. 
# The entry contains a value from 2D array, 
# row and column numbers of the value 
class HeapNode: 
    def __init__(self, val, r, c): 
        self.val = val # value to be stored 
        self.r = r # Row number of value in 2D array 
        self.c = c # Column number of value in 2D array 
 
# A utility function to minheapify the node harr[i] 
# of a heap stored in harr[] 
def minHeapify(harr, i, heap_size): 
    l = i * 2 + 1
    r = i * 2 + 2
    if(l < heap_size and r<heap_size and harr[l].val < harr[i].val and harr[r].val < harr[i].val):
      temp= HeapNode(0,0,0)
      temp=harr[r]
      harr[r]=harr[i]
      harr[i]=harr[l]
      harr[l]=temp
      minHeapify(harr ,l,heap_size)
      minHeapify(harr ,r,heap_size)
    if (l < heap_size and harr[l].val < harr[i].val):
      temp= HeapNode(0,0,0)
      temp=harr[i]
      harr[i]=harr[l]
      harr[l]=temp
      minHeapify(harr ,l,heap_size)
             
# This function returns kth smallest element 
# in a 2D array mat[][] 
def kthSmallest(mat, n, k): 
 
    # k must be greater than 0 and smaller than n*n 
    if k < 0 or k > n * n: 
        return maxsize 
 
    # Create a min heap of elements from 
    # first row of 2D array 
    harr = [0] * n 
    for i in range(n): 
        harr[i] = HeapNode(mat[0][i], 0, i) 
 
    hr = HeapNode(0, 0, 0) 
    for i in range(k): 
 
        # Get current heap root 
        hr = harr[0] 
 
        # Get next value from column of root's value. 
        # If the value stored at root was last value 
        # in its column, then assign INFINITE as next value 
        nextval = mat[hr.r + 1][hr.c] if (hr.r < n - 1) else maxsize 
 
        # Update heap root with next value 
        harr[0] = HeapNode(nextval, hr.r + 1, hr.c) 
 
        # Heapify root 
        minHeapify(harr, 0, n) 
 
    # Return the value at last extracted root 
    return hr.val 
 
# Driver Code 
if __name__ == "__main__": 
    mat = [[10, 20, 30, 40], 
        [15, 25, 35, 45], 
        [25, 29, 37, 48], 
        [32, 33, 39, 50]] 
    print("7th smallest element is", 
            kthSmallest(mat, 4, 7)) 
 
# This code is contributed by Rishabh Chauhan

C#

// C# program for kth largest element in a 2d 
// array sorted row-wise and column-wise 
using System;
 
class GFG{
     
// A structure to store entry of heap.
// The entry contains value from 2D array,
// row and column numbers of the value 
class HeapNode
{
     
    // Value to be stored 
    public int val;
     
    // Row number of value in 2D array 
    public int r;
     
    // Column number of value in 2D array 
    public int c;
     
    public HeapNode(int val, int r, int c)
    {
        this.val = val;
        this.c = c;
        this.r = r;
    }
}
 
// A utility function to minheapify the node
// harr[i] of a heap stored in harr[] 
static void minHeapify(HeapNode []harr, int i, int heap_size){
    int l = 2 * i + 1;
    int r = 2 * i + 2;
   
    if(l < heap_size && r < heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){
            HeapNode temp = new HeapNode(0, 0, 0); 
            temp=harr[r];
            harr[r]=harr[i];
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
            minHeapify(harr ,r,heap_size);
        }
          if (l < heap_size && harr[l].val < harr[i].val){
            HeapNode temp = new HeapNode(0, 0, 0);    
            temp = harr[i];
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
        }
}
 
// This function returns kth smallest
// element in a 2D array [,]mat 
public static int kthSmallest(int[,] mat,int n, int k)
{
     
    // k must be greater than 0 and 
    // smaller than n*n 
    if (k < 0 || k > n * n)
    {
        return int.MaxValue;
    }
     
    // Create a min heap of elements 
    // from first row of 2D array 
    HeapNode []harr = new HeapNode[n];
     
    for(int i = 0; i < n; i++)
    {
        harr[i] = new HeapNode(mat[0, i], 0, i);
    }
     
    HeapNode hr = new HeapNode(0, 0, 0);
     
    for(int i = 0; i < k; i++)
    {
         
        // Get current heap root 
        hr = harr[0];
         
        // Get next value from column of root's
        // value. If the value stored at root was
        // last value in its column, then assign
        // INFINITE as next value 
        int nextVal = hr.r < n - 1 ? 
                      mat[hr.r + 1, hr.c] :
                      int.MaxValue;
                       
        // Update heap root with next value 
        harr[0] = new HeapNode(nextVal, hr.r + 1, hr.c);
                                
        // Heapify root 
        minHeapify(harr, 0, n);
    }
     
    // Return the value at last
    // extracted root 
    return hr.val;
}
 
// Driver code
public static void Main(String []args)
{
    int [,]mat = { { 10, 20, 30, 40 },
                   { 15, 25, 35, 45 },
                   { 25, 29, 37, 48 },
                   { 32, 33, 39, 50 } };
                     
    int res = kthSmallest(mat, 4, 7);
     
    Console.Write("7th smallest element is " + res);
}
}
 
// This code is contributed by Rishabh Chauhan

Javascript

<script>
// Javascript program for kth largest element in a 2d
// array sorted row-wise and column-wise
 
// A structure to store entry of heap.
// The entry contains value from 2D array,
// row and column numbers of the value
class HeapNode
{
    constructor(val,r,c)
    {
        this.val = val;
        this.c = c;
        this.r = r;
    }
}
 
// A utility function to minheapify the node
// harr[i] of a heap stored in harr[]
function minHeapify(harr,i,heap_size)
{
    let l = 2 * i + 1;
    let r = 2 * i + 2;
    let min = i;
      
    if(l < heap_size&& r<heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){
            let temp=harr[r];
            harr[r]=harr[i];
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
            minHeapify(harr ,r,heap_size);
        }
          if (l < heap_size && harr[l].val < harr[i].val){
            let temp=harr[i];           
            harr[i]=harr[l];
            harr[l]=temp;
            minHeapify(harr ,l,heap_size);
        }
}
 
// This function returns kth smallest
// element in a 2D array mat[][]
function kthSmallest(mat,n,k)
{
    // k must be greater than 0 and
    // smaller than n*n
    if (k < 0 && k >= n * n)
        return Number.MAX_VALUE;
      
    // Create a min heap of elements
    // from first row of 2D array
    let harr = new Array(n);
      
    for(let i = 0; i < n; i++)
    {
        harr[i] = new HeapNode(mat[0][i], 0, i);
    }
      
    let hr = new HeapNode(0, 0, 0);
      
    for(let i = 1; i <= k; i++)
    {
          
        // Get current heap root
        hr = harr[0];
          
        // Get next value from column of root's
        // value. If the value stored at root was
        // last value in its column, then assign
        // INFINITE as next value
        let nextVal = hr.r < n - 1 ?
                      mat[hr.r + 1][hr.c] :
                      Number.MAX_VALUE;
                        
        // Update heap root with next value
        harr[0] = new HeapNode(nextVal,
                               hr.r + 1, hr.c);
                                 
        // Heapify root
        minHeapify(harr, 0, n);
    }
      
    // Return the value at last extracted root
    return hr.val;
}
 
// Driver code
let mat=[[ 10, 20, 30, 40 ],
                    [ 15, 25, 35, 45 ],
                    [ 25, 29, 37, 48 ],
                    [ 32, 33, 39, 50 ]];
let res = kthSmallest(mat, 4, 7);
document.write("7th smallest element is "+ res);
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

7th smallest element is 30

The codes above are contributed by RISHABH CHAUHAN.
Complexity Analysis:

Time Complexity: The above solution involves following steps.
1. Building a min-heap which takes O(n) time
2. Heapify k times which takes O(k Logn) time.
Auxiliary Space: O(R), where R is the length of a row, as the Min-Heap stores one row at a time.

The above code can be optimized to build a heap of size k when k is smaller than n. In that case, the kth smallest element must be in first k rows and k columns.
We will soon be publishing more efficient algorithms for finding the kth smallest element.
This article is compiled by Ravi Gupta. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Using inbuilt priority_queue :

By using a comparator, we can carry out custom comparison in priority_queue. We will use priority_queue<pair<int,int>> for this.

Implementation :

C++

// kth largest element in a 2d array sorted row-wise and
// column-wise
#include<bits/stdc++.h>
using namespace std;
 
int kthSmallest(int mat[4][4], int n, int k)
{
    // USING LAMBDA FUNCTION
    // [=] IN LAMBDA FUNCTION IS FOR CAPTURING VARIABLES WHICH 
    // ARE OUT OF SCOPE i.e. mat[r]
    // NOW, IT'LL COMPARE ELEMENTS OF HEAP BY ELEMENTS AT mat[first][second]
      // Capturing the value of mat by reference to prevent copying
    auto cmp = [&](pair<int,int> a,pair<int,int> b){
        return mat[a.first][a.second] > mat[b.first][b.second];
    };
     
    //DECLARING priority_queue AND PUSHING FIRST ROW IN IT
    priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp);
    for(int i=0; i<n; i++){
        pq.push({i,0});
    }
     
    //RUNNING LOOP FOR (k-1) TIMES
    for(int i=1; i<k; i++){
        auto p = pq.top();
        pq.pop();
         
        //AFTER POPPING, WE'LL PUSH NEXT ELEMENT OF THE ROW IN THE HEAP
        if(p.second+1 < n) pq.push({p.first,p.second + 1});
    }
    // ON THE k'th ITERATION, pq.top() will be our answer.
    return mat[pq.top().first][pq.top().second];
}
 
// driver program to test above function
int main()
{
    int mat[4][4] = {
        { 10, 20, 30, 40 },
        { 15, 25, 35, 45 },
        { 25, 29, 37, 48 },
        { 32, 33, 39, 50 },
    };
    cout << "7th smallest element is "
        << kthSmallest(mat, 4, 7);
    return 0;
}

Java

// kth largest element in a 2d array sorted row-wise and
// column-wise
import java.util.*;
 
public class GFG {
 
  static class pair {
    int first, second;
    pair(int f, int s)
    {
      first = f;
      second = s;
    }
  }
  static int kthSmallest(int mat[][], int n, int k)
  {
    // USING LAMBDA FUNCTION
    // [=] IN LAMBDA FUNCTION IS FOR CAPTURING VARIABLES
    // WHICH ARE OUT OF SCOPE i.e. mat[r] NOW, IT'LL
    // COMPARE ELEMENTS OF HEAP BY ELEMENTS AT
    // mat[first][second] Capturing the value of mat by
    // reference to prevent copying
 
    // DECLARING priority_queue AND PUSHING FIRST ROW IN
    // IT
    PriorityQueue<pair> pq
      = new PriorityQueue<>((pair a, pair b) -> {
        return mat[a.first][a.second]
          - mat[b.first][b.second];
      });
 
    for (int i = 0; i < n; i++) {
      pq.add(new pair(i, 0));
    }
 
    // RUNNING LOOP FOR (k-1) TIMES
    for (int i = 1; i < k; i++) {
      pair p = pq.peek();
      pq.remove();
 
      // AFTER POPPING, WE'LL PUSH NEXT ELEMENT OF THE
      // ROW IN THE HEAP
      if (p.second + 1 < n)
        pq.add(new pair(p.first, p.second + 1));
    }
    // ON THE k'th ITERATION, pq.top() will be our
    // answer.
    return mat[pq.peek().first][pq.peek().second];
  }
 
  // driver program to test above function
  public static void main(String[] args)
  {
    int mat[][] = {
      { 10, 20, 30, 40 },
      { 15, 25, 35, 45 },
      { 25, 29, 37, 48 },
      { 32, 33, 39, 50 },
    };
    System.out.println("7th smallest element is "
                       + kthSmallest(mat, 4, 7));
  }
}
 
// This code is contributed by Karandeep1234

Python3

# kth largest element in a 2d array sorted row-wise and
# column-wise
 
import heapq
 
def kthSmallest(mat, n, k):
    # Using lambda function
    # [=] in lambda function is for capturing variables which are out of scope i.e. mat[r]
    # Now, it'll compare elements of heap by elements at mat[first][second]
    # Capturing the value of mat by reference to prevent copying
    cmp = lambda a,b: mat[a[0]][a[1]] - mat[b[0]][b[1]]
 
    # Declaring heap and pushing first element of each row in it
    heap = [(mat[i][0], i, 0) for i in range(n)]
    heapq.heapify(heap)
 
    # Running loop for k-1 times
    for i in range(k-1):
        val, row, col = heapq.heappop(heap)
 
        # After popping, we'll push next element of the row in the heap
        if col < n-1:
            heapq.heappush(heap, (mat[row][col+1], row, col+1))
 
    # On the k'th iteration, heap[0] will be our answer
    return heap[0][0]
 
# Driver program to test above function
mat = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [25, 29, 37, 48],
    [32, 33, 39, 50]
]
 
print("7th smallest element is", kthSmallest(mat, 4, 7))

C#

// kth largest element in a 2d array sorted row-wise and
// column-wise
using System;
using System.Collections.Generic;
 
public class GFG
{
    static int kthSmallest(int[,] mat, int n, int k)
    {
        // USING LAMBDA FUNCTION
        // [=] IN LAMBDA FUNCTION IS FOR CAPTURING VARIABLES WHICH 
        // ARE OUT OF SCOPE i.e. mat[r]
        // NOW, IT'LL COMPARE ELEMENTS OF HEAP BY ELEMENTS AT mat[first][second]
        // Capturing the value of mat by reference to prevent copying
        Comparison<(int, int)> cmp = (a, b) => mat[a.Item1, a.Item2].CompareTo(mat[b.Item1, b.Item2]);
 
        //DECLARING priority_queue AND PUSHING FIRST ROW IN IT
        var pq = new PriorityQueue<(int, int)>(cmp);
        for (int i = 0; i < n; i++)
        {
            pq.Enqueue((i, 0));
        }
 
        //RUNNING LOOP FOR (k-1) TIMES
        for (int i = 1; i < k; i++)
        {
            var p = pq.Peek();
            pq.Dequeue();
 
            //AFTER POPPING, WE'LL PUSH NEXT ELEMENT OF THE ROW IN THE HEAP
            if (p.Item2 + 1 < n) pq.Enqueue((p.Item1, p.Item2 + 1));
        }
        // ON THE k'th ITERATION, pq.top() will be our answer.
        return mat[pq.Peek().Item1, pq.Peek().Item2];
    }
 
    // driver program to test above function
    public static void Main()
    {
        int[,] mat = {
            { 10, 20, 30, 40 },
            { 15, 25, 35, 45 },
            { 25, 29, 37, 48 },
            { 32, 33, 39, 50 },
        };
        Console.WriteLine("7th smallest element is " + kthSmallest(mat, 4, 7));
    }
}
 
public class PriorityQueue<T>
{
    private Comparison<T> _comparer;
    private List<T> _heap = new List<T>();
 
    public PriorityQueue() { _comparer = Comparer<T>.Default.Compare; }
    public PriorityQueue(Comparison<T> comparer) { _comparer = comparer; }
 
    public void Enqueue(T item)
    {
        _heap.Add(item);
        int i = _heap.Count - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (_comparer(_heap[parent], _heap[i]) <= 0)
                break;
 
            T tmp = _heap[parent];
            _heap[parent] = _heap[i];
            _heap[i] = tmp;
 
            i = parent;
        }
    }
 
    public T Dequeue()
    {
        int last = _heap.Count - 1;
        T frontItem = _heap[0];
        _heap[0] = _heap[last];
        _heap.RemoveAt(last);
 
        --last;
        int i = 0;
        while (true)
        {
            int child = i * 2 + 1;
            if (child > last)
                break;
 
            if (child + 1 <= last && _comparer(_heap[child], _heap[child + 1]) > 0)
                child++;
 
                     if (_comparer(_heap[i], _heap[child]) > 0)
            {
                T tmp = _heap[i];
                _heap[i] = _heap[child];
                _heap[child] = tmp;
            }
            else
                break;
 
            i = child;
    }
 
    return frontItem;
}
 
public T Peek() { return _heap[0]; }
 
public int Count { get { return _heap.Count; } }
 
public bool Any() { return _heap.Count > 0; }
}

Javascript

// Javascript code 
// kth smallest element in a 2d array sorted row-wise and
// column-wise
 
function kthSmallest(mat, n, k) {
  // Define a compare function to compare elements of the heap
  const cmp = (a, b) => mat[a[0]][a[1]] < mat[b[0]][b[1]];
   
  // Initialize the heap with the first column
  let heap = [];
  for (let i = 0; i < n; i++) {
    heap.push([i, 0]);
  }
   
  // Run the loop k-1 times
  for (let i = 1; i < k; i++) {
    // Get the smallest element from the heap
    let [r, c] = heap[0];
     
    // If the element has a next element in the row, add it to the heap
    if (c + 1 < n) {
      heap[0] = [r, c+1];
    } else {
      // If the element is the last in the row, remove it from the heap
      heap[0] = heap[heap.length - 1];
      heap.pop();
    }
     
    // Re-heapify the heap
    let j = 0;
    while (2*j+1 < heap.length) {
      let left = 2*j+1;
      let right = 2*j+2 < heap.length ? 2*j+2 : left;
      let minChild = cmp(heap[left], heap[right]) ? left : right;
      if (cmp(heap[minChild], heap[j])) {
        [heap[j], heap[minChild]] = [heap[minChild], heap[j]];
        j = minChild;
      } else {
        break;
      }
    }
  }
   
  // Return the kth smallest element
  let [r, c] = heap[0];
  return mat[r];
}
 
// Example usage
let mat = [  [10, 20, 30, 40],
  [15, 25, 35, 45],
  [25, 29, 37, 48],
  [32, 33, 39, 50],
];
console.log("7th smallest element is " + kthSmallest(mat, 4, 7)); 

Output

7th smallest element is 30

Time Complexity: O(n log n)
Auxiliary Space: O(n)

Using Binary Search over the Range:

This approach uses binary search to iterate over possible solutions. We know that

answer >= mat[0][0]
answer <= mat[N-1][N-1]

So we do a binary search on this range and in each iteration determine the no of elements greater than or equal to our current middle element. The elements greater than or equal to current element can be found in O( n logn ) time using binary search.

C++

#include <bits/stdc++.h>
using namespace std;
 
// This returns count of elements in matrix less than of equal to num
int getElementsGreaterThanOrEqual(int num, int n, int mat[4][4]) {
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        // if num is less than the first element then no more element in matrix
        // further are less than or equal to num
        if (mat[i][0] > num) {
            return ans;
        }
        // if num is greater than last element, it is greater than all elements
        // in that row
        if (mat[i][n - 1] <= num) {
            ans += n;
            continue;
        }
        // This contain the col index of last element in matrix less than of equal
        // to num
        int greaterThan = 0;
        for (int jump = n / 2; jump >= 1; jump /= 2) {
            while (greaterThan + jump < n &&
                   mat[i][greaterThan + jump] <= num) {
                greaterThan += jump;
            }
        }
 
        ans += greaterThan + 1;
    }
    return ans;
}
 
// returns kth smallest index in the matrix
int kthSmallest(int mat[4][4], int n, int k) {
    //  We know the answer lies between the first and the last element
    // So do a binary search on answer based on the number of elements
    // our current element is greater than the elements in the matrix
    int l = mat[0][0], r = mat[n - 1][n - 1];
 
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat);
 
        if (greaterThanOrEqualMid >= k)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return l;
}
 
int main() {
    int n = 4;
    int mat[4][4] = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {25, 29, 37, 48},
        {32, 33, 39, 50},
    };
    cout << "7th smallest element is " << kthSmallest(mat, 4, 7);
    return 0;
}

Java

import java.io.*;
 
class GFG {
 
  // This returns count of elements in 
  // matrix less than of equal to num
  static int getElementsGreaterThanOrEqual(int num, int n, int mat[][]) 
  {
    int ans = 0;
 
    for (int i = 0; i < n; i++)
    {
       
      // if num is less than the first element 
      // then no more element in matrix
      // further are less than or equal to num
      if (mat[i][0] > num) {
        return ans;
      }
       
      // if num is greater than last element, 
      // it is greater than all elements
      // in that row
      if (mat[i][n - 1] <= num) {
        ans += n;
        continue;
      }
       
      // This contain the col index of last element
      // in matrix less than of equal
      // to num
      int greaterThan = 0;
      for (int jump = n / 2; jump >= 1; jump /= 2) {
        while (greaterThan + jump < n &&
               mat[i][greaterThan + jump] <= num) {
          greaterThan += jump;
        }
      }
 
      ans += greaterThan + 1;
    }
    return ans;
  }
 
  // returns kth smallest index in the matrix
  static int kthSmallest(int mat[][], int n, int k)
  {
     
    // We know the answer lies between the first and the last element
    // So do a binary search on answer based on the number of elements
    // our current element is greater than the elements in the matrix
    int l = mat[0][0], r = mat[n - 1][n - 1];
 
    while (l <= r) {
      int mid = l + (r - l) / 2;
      int greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat);
 
      if (greaterThanOrEqualMid >= k)
        r = mid - 1;
      else
        l = mid + 1;
    }
    return l;
  }
 
  public static void main(String args[]) {
    int mat[][] = {
      { 10, 20, 30, 40 },
      { 15, 25, 35, 45 },
      { 25, 29, 37, 48 },
      { 32, 33, 39, 50 },
    };
    System.out.println("7th smallest element is " + kthSmallest(mat, 4, 7));
  }
 
}
 
// This code is contributed by gfgking.

Python3

# This returns count of elements in matrix
# less than of equal to num
def getElementsGreaterThanOrEqual(num,n,mat): 
    ans = 0
    for i in range(n):
       
        # if num is less than the first element 
        # then no more element in matrix
        # further are less than or equal to num
        if (mat[i][0] > num):
            return ans
           
        # if num is greater than last element, 
        # it is greater than all elements
        # in that row
        if (mat[i][n - 1] <= num):
            ans += n
            continue
        # This contain the col index of last element 
        # in matrix less than of equal
        # to num
        greaterThan = 0
        jump = n // 2
        while(jump >= 1):
                while (greaterThan + jump < n and mat[i][greaterThan + jump] <= num):
                    greaterThan += jump
                jump //= 2
 
        ans += greaterThan + 1
    return ans
 
# returns kth smallest index in the matrix
def kthSmallest(mat, n, k): 
 
    # We know the answer lies between 
    # the first and the last element
    # So do a binary search on answer 
    # based on the number of elements
    # our current element is greater than
    # the elements in the matrix
    l,r = mat[0][0],mat[n - 1][n - 1]
 
    while (l <= r):
        mid = l + (r - l) // 2
        greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat)
 
        if (greaterThanOrEqualMid >= k):
            r = mid - 1
        else:
            l = mid + 1
 
    return l
 
# driver code
n = 4
mat = [[10, 20, 30, 40],[15, 25, 35, 45],[25, 29, 37, 48],[32, 33, 39, 50]]
print(f"7th smallest element is {kthSmallest(mat, 4, 7)}")
 
# This code is contributed by shinjanpatra

C#

using System;
 
public class GFG
{
 
  // This returns count of elements in 
  // matrix less than of equal to num
  static int getElementsGreaterThanOrEqual(int num, int n, int [,]mat) 
  {
    int ans = 0;
 
    for (int i = 0; i < n; i++)
    {
 
      // if num is less than the first element 
      // then no more element in matrix
      // further are less than or equal to num
      if (mat[i,0] > num) {
        return ans;
      }
 
      // if num is greater than last element, 
      // it is greater than all elements
      // in that row
      if (mat[i,n - 1] <= num) {
        ans += n;
        continue;
      }
 
      // This contain the col index of last element
      // in matrix less than of equal
      // to num
      int greaterThan = 0;
      for (int jump = n / 2; jump >= 1; jump /= 2) {
        while (greaterThan + jump < n &&
               mat[i,greaterThan + jump] <= num) {
          greaterThan += jump;
        }
      }
 
      ans += greaterThan + 1;
    }
    return ans;
  }
 
  // returns kth smallest index in the matrix
  static int kthSmallest(int [,]mat, int n, int k)
  {
 
    // We know the answer lies between the first and the last element
    // So do a binary search on answer based on the number of elements
    // our current element is greater than the elements in the matrix
    int l = mat[0,0], r = mat[n - 1,n - 1];
 
    while (l <= r) {
      int mid = l + (r - l) / 2;
      int greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat);
 
      if (greaterThanOrEqualMid >= k)
        r = mid - 1;
      else
        l = mid + 1;
    }
    return l;
  }
 
  public static void Main(String []args) {
    int [,]mat = {
      { 10, 20, 30, 40 },
      { 15, 25, 35, 45 },
      { 25, 29, 37, 48 },
      { 32, 33, 39, 50 },
    };
    Console.WriteLine("7th smallest element is " + kthSmallest(mat, 4, 7));
  }
 
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
    // This returns count of elements in matrix
    // less than of equal to num
    function getElementsGreaterThanOrEqual(num,n,mat) 
    {
        let ans = 0
 
        for (let i = 0; i < n; i++) {
            // if num is less than the first element 
            // then no more element in matrix
            // further are less than or equal to num
            if (mat[i][0] > num) {
                return ans;
            }
            // if num is greater than last element, 
            // it is greater than all elements
            // in that row
            if (mat[i][n - 1] <= num) {
                ans += n;
                continue;
            }
            // This contain the col index of last element 
            // in matrix less than of equal
            // to num
            let greaterThan = 0;
            for (let jump = n / 2; jump >= 1; jump /= 2) {
                while (greaterThan + jump < n &&
                    mat[i][greaterThan + jump] <= num) {
                    greaterThan += jump;
                }
            }
 
            ans += greaterThan + 1;
        }
        return ans;
    }
 
    // returns kth smallest index in the matrix
    function kthSmallest(mat,n,k) 
    {
        // We know the answer lies between 
        // the first and the last element
        // So do a binary search on answer 
        // based on the number of elements
        // our current element is greater than
        // the elements in the matrix
        let l = mat[0][0], r = mat[n - 1][n - 1];
 
        while (l <= r) {
            let mid = l + parseInt((r - l) / 2, 10);
            let greaterThanOrEqualMid = 
            getElementsGreaterThanOrEqual(mid, n, mat);
 
            if (greaterThanOrEqualMid >= k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
 
 
    let n = 4;
    let mat = [
        [10, 20, 30, 40],
        [15, 25, 35, 45],
        [25, 29, 37, 48],
        [32, 33, 39, 50],
    ];
    document.write("7th smallest element is " + 
    kthSmallest(mat, 4, 7));
     
</script>

Output

7th smallest element is 30

Complexity Analysis

Time Complexity : O( y * n*logn)

Where y =  log( abs(Mat[0][0] - Mat[n-1][n-1]) )

We call the getElementsGreaterThanOrEqual function log ( abs(Mat[0][0] – Mat[n-1][n-1]) ) times
Time complexity of getElementsGreaterThanOrEqual is O(n logn) since there we do binary search n times.

Auxiliary Space: O(1)

USING ARRAY:

We will make a new array and will copy all the contents of matrix in this array. After that we will sort that array and find kth smallest element. This will be so easier.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
int kthSmallest(int mat[4][4], int n, int k)
{
 
  int a[n*n];
  int v = 0;
 
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < n; j++)
    {
      a[v] = mat[i][j];
      v++;
    }
  } 
 
  sort(a, a + (n*n));
  int result = a[k - 1];
  return result;
}
 
// Driver code
int main()
{
  int mat[4][4] = { { 10, 20, 30, 40 },
                   { 15, 25, 35, 45 },
                   { 25, 29, 37, 48 },
                   { 32, 33, 39, 50 } };
  int res = kthSmallest(mat, 4, 7);
 
  cout <<  "7th smallest element is " << res;
  return 0;
}
 
// This code is contributed by sanjoy_62.

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
    public static void main (String[] args) {
         
    int mat[][] = { { 10, 20, 30, 40 },
                    { 15, 25, 35, 45 },
                    { 25, 29, 37, 48 },
                    { 32, 33, 39, 50 } };
      int res = kthSmallest(mat, 4, 7);
       
    System.out.print("7th smallest element is "+ res);
    }
   
   static int kthSmallest(int[][]mat,int n,int k)
    {
          
       int[] a=new int[n*n];
       int v=0;
        
       for(int i=0;i<n;i++){
           for(int j=0;j<n;j++){
               a[v]=mat[i][j];
               v++;
           }
       } 
         
        Arrays.sort(a);
        int result=a[k-1];
        return result;
    }
}

Python3

# Python program to implement above approach
def kthSmallest(mat, n, k):
         
    a = [0 for i in range(n*n)]
    v=0
         
    for i in range(n):
        for j in range(n):
            a[v] = mat[i][j]
            v += 1
             
    a.sort()
    result = a[k - 1]
    return result
 
# driver program
         
mat = [ [ 10, 20, 30, 40 ],
            [ 15, 25, 35, 45 ],
            [ 25, 29, 37, 48 ],
            [ 32, 33, 39, 50 ] ]
res = kthSmallest(mat, 4, 7)
     
print("7th smallest element is "+ str(res))
 
# This code is contributed by shinjanpatra

C#

/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
 
public class GFG {
  public static void Main(String[] args) {
 
    int [,]mat = { { 10, 20, 30, 40 },
                  { 15, 25, 35, 45 },
                  { 25, 29, 37, 48 },
                  { 32, 33, 39, 50 } };
    int res = kthSmallest(mat, 4, 7);
 
    Console.Write("7th smallest element is "+ res);
  }
 
  static int kthSmallest(int[,]mat, int n, int k)
  {
 
    int[] a = new int[n*n];
    int v = 0;
 
    for(int i = 0; i < n; i++)
    {
      for(int j = 0; j < n; j++)
      {
        a[v] = mat[i, j];
        v++;
      }
    } 
 
    Array.Sort(a);
    int result = a[k - 1];
    return result;
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to implement above approach
function kthSmallest(mat, n, k)
{
         
    let a = new Array(n*n)
    let v=0
         
    for(let i = 0; i < n; i++)
    {
        for(let j = 0; j < n; j++)
        {
            a[v] = mat[i][j];
            v++;
        }
    }
         
    a.sort();
    let result = a[k - 1];
    return result;
}
 
// driver program
         
let mat = [ [ 10, 20, 30, 40 ],
            [ 15, 25, 35, 45 ],
            [ 25, 29, 37, 48 ],
            [ 32, 33, 39, 50 ] ]
let res = kthSmallest(mat, 4, 7)
     
document.write("7th smallest element is "+ res,"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

Output

7th smallest element is 30

Time Complexity: O(N2log(N2)) , We have array of N2 elements,for sorting them time will be N2log(N2).
Auxiliary Space: O(N²)

Using Priority queue approach

C++14

#include <bits/stdc++.h>
using namespace std;
int kthSmallest(vector<vector<int>>& matrix, int k) {
  //n = size of matrix
  int i,j,n=matrix.size();
   
  //using built-in priority queue which acts as max Heap i.e. largest element will be on top
  //Kth smallest element can also be seen as largest element in a priority queue of size k
  //By this logic we pop elements from priority queue when its size becomes greater than k
  //thus top of priority queue is kth smallest element in matrix
   
  priority_queue<int> maxH;
  if(k==1)
    return matrix[0][0];
   
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      maxH.push(matrix[i][j]);
      if(maxH.size()>k)
        maxH.pop();
    }
  }
   
  return maxH.top();
}
int main() {
 
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
      int k = 8;
    cout << "8th smallest element is " << kthSmallest(matrix,k);
    return 0;
}

Java

import java.util.*;
import java.io.*;
 
public class Main {
  public static int kthSmallest(int[][] matrix, int k)
  {
     
    // n = size of matrix
    int i, j, n = matrix.length;
 
    // using built-in priority queue which acts as max
    // Heap i.e. largest element will be on top
    // Kth smallest element can also be seen as largest
    // element in a priority queue of size k By this
    // logic we pop elements from priority queue when
    // its size becomes greater than k thus top of
    // priority queue is kth smallest element in matrix
 
    PriorityQueue<Integer> maxH = new PriorityQueue<>(
      Collections.reverseOrder());
    if (k == 1)
      return matrix[0][0];
 
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        maxH.add(matrix[i][j]);
        if (maxH.size() > k)
          maxH.poll();
      }
    }
 
    return maxH.peek();
  }
  public static void main(String[] args)
  {
    int[][] matrix = { { 1, 5, 9 },
                      { 10, 11, 13 },
                      { 12, 13, 15 } };
    int k = 8;
    System.out.print("8th smallest element is "
                     + kthSmallest(matrix, k));
  }
}
 
// This code is contributed by tapeshdua420.

Python3

import heapq
 
 
def kthSmallest(matrix, k):
    # n = size of matrix
    n = len(matrix)
 
    # using built-in priority queue which acts as max Heap i.e. largest element will be on top
    # Kth smallest element can also be seen as largest element in a priority queue of size k
    # By this logic we pop elements from priority queue when its size becomes greater than k
    # thus top of priority queue is kth smallest element in matrix
 
    maxH = []
    for i in range(n):
        for j in range(n):
            heapq.heappush(maxH, -matrix[i][j])
            if len(maxH) > k:
                heapq.heappop(maxH)
    return -maxH[0]
 
 
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
k = 8
print("8th smallest element is", kthSmallest(matrix, k))
 
# This code is contributed by Tapesh (tapeshdua420)

C#

using System;
using System.Collections.Generic;
 
public class GFG {
  public static int kthSmallest(int[,] matrix, int k)
  {
 
    // n = size of matrix
    int i, j, n = matrix.GetLength(0);
 
    // using built-in priority queue which acts as max
    // Heap i.e. largest element will be on top
    // Kth smallest element can also be seen as largest
    // element in a priority queue of size k By this
    // logic we pop elements from priority queue when
    // its size becomes greater than k thus top of
    // priority queue is kth smallest element in matrix
 
    List<int> maxH = new List<int>();
    if (k == 1)
      return matrix[0,0];
 
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        maxH.Add(matrix[i,j]);
        if (maxH.Count > k){
          maxH.Sort((a, b) => b.CompareTo(a));
          maxH.RemoveAt(0);
        }
      }
    }
    maxH.Sort((a, b) => b.CompareTo(a));
    return maxH[0];
  }
  public static void Main(String[] args)
  {
    int[,] matrix = { { 1, 5, 9 },
                     { 10, 11, 13 },
                     { 12, 13, 15 } };
    int k = 8;
    Console.Write("8th smallest element is "
                  + kthSmallest(matrix, k));
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
function kthSmallest(matrix, k) {
    //n = size of matrix
    let i;
    let j;
    let n = matrix.length;
   
    //using built-in priority queue which acts as max Heap i.e. largest element will be on top
    //Kth smallest element can also be seen as largest element in a priority queue of size k
    //By this logic we pop elements from priority queue when its size becomes greater than k
    //thus top of priority queue is kth smallest element in matrix
   
    maxH = [];
    // priority_queue<int> maxH;
    if(k==1) return matrix[0][0];
   
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            maxH.push(matrix[i][j]);
            maxH.sort((a, b) => (b-a));
             
            if(maxH.length>k) maxH.shift();
        }
    }
   
    return maxH[0];
}
 
let matrix = [[1,5,9],[10,11,13],[12,13,15]];
let k = 8;
document.write("8th smallest element is " + kthSmallest(matrix,k));
 
// The code is contributed by Nidhi goel. 
</script>

Output

8th smallest element is 13

Time Complexity: O(log(k)*n²)
Auxiliary Space: O(n)

This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Kth smallest element in a row-wise and column-wise sorted 2D array

BRUTE METHOD:

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Using Binary Search over the Range:

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++14

Java

Python3

C#

Javascript

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US