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

Software Development
#1

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[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;

}

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.