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

Hello Everyone,

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

Algorithm:

1. The idea is to use min heap. Create a Min-Heap to store the elements
2. 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.
3. Now Run a loop k times to extract min element from heap in each iteration
4. Get minimum element (or root) from Min-Heap.
5. Find row number and column number of the minimum element.
6. Replace root with the next element from same column and min-heapify the root.
7. Print the last extracted element, which is the kth minimum element

Implementation:

`// kth largest element in a 2d array sorted row-wise and`

`// column-wise`

`#include`

`#include`

`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 swap two HeapNode items.`

`void` `swap(HeapNode* x, HeapNode* y)`

`{`

` ` `HeapNode z = *x;`

` ` `*x = *y;`

` ` `*y = z;`

`}`

`// 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;`

` ` `int` `smallest = i;`

` ` `if` `(l < heap_size && harr[l].val < harr[i].val)`

` ` `smallest = l;`

` ` `if` `(r < heap_size && harr[r].val = 0) {`

` ` `minHeapify(harr, i, n);`

` ` `i--;`

` ` `}`

`}`

`// This function returns kth`

`// smallest element in a 2D array`

`// mat[][]`

`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_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[i], 0, i };`

` ` `HeapNode hr;`

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

` ` `// Get current heap root`

` ` `hr = harr;`

` ` `// 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 = { 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 = {`

` ` `{ 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;`

`}`

Output:

7th smallest element is 30

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.
• Space Complexity: O®, where R is the length of a row, as the Min-Heap stores one row at a time.