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

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

Kth-smallest-element

#include<iostream>

#include<stdio.h>

#include<climits>

using namespace std;

typedef struct HeapNode

{

    int value;

    int row;

    int col;

}node;

void minHeapify(node arr[], int n ,int heap_size);

void swap_elements(node *x, node *y);

void  HeapSort(node arr[], int n);

int FindKthElement(int arr[4][4],int n,int k);

void swap_elements(node *x, node *y)

{

    node z = *x;

    *x= *y;

    *y=z;

}

void minHeapify(node arr[], int n ,int heap_size)

{

    int left = 2*n+1;

    int right = 2*n+2;

    int small =n;

    if(left<heap_size && arr[left].value < arr[n].value)

        small =left;

    if(right<heap_size && arr[right].value < arr[small].value)

        small =right;

    if(small !=n)

    {

        swap_elements(&arr[small], &arr[n]);

        minHeapify(arr,small,  heap_size);

    }

}

void  HeapSort(node arr[], int n)

{

    int i= (n-1)/2;

    while(i>=0)

    {

      minHeapify(arr, i, n);

      i--;

    }

}

int FindKthElement(int  arr[4][4],int n,int k)

{

    int next_value =0;

    if(k<=0 || k>n*n)

     return INT_MAX;

    node temp_Arr[n];

    /*creating heap for first row elements*/

   for (int i = 0; i < n; i++)

        temp_Arr[i] = {arr[0][i], 0, i};

    HeapSort(temp_Arr, n);

    node Next_value_array;

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

    {

        Next_value_array = temp_Arr[0];

        if(Next_value_array.row<(n-1))

        {

            next_value = arr[Next_value_array.row + 1][Next_value_array.col];

        }

        else

        {

            next_value = INT_MAX;

        }

        //int next_value = (Next_value_array.row<(n-1)) ? arr[Next_value_array.row + 1][Next_value_array.col]:INT_MAX;

        temp_Arr[0] =  {next_value, Next_value_array.row+1, Next_value_array.col };

        minHeapify(temp_Arr,0, n);

    }

    return Next_value_array.value;

}

int main()

{

    int arr[4][4] = { {10, 20, 30, 40},

                    {15, 25, 35, 45},

                    {25, 29, 37, 48},

                    {32, 33, 39, 50},

                  };

  cout << "7th smallest element is " << FindKthElement(arr, 4, 7);

  return 0;

}

Refer link for more details

Other Articles:

Merge Two link List , Find merge point of two linked list.

Other Blogs: Click here