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

Compare two strings represented as linked lists

Compare two strings represented as linked lists

Compare Strings

#include<iostream>

#include<stdio.h>

using namespace std;

typedef struct Node

{

    char data;

    struct Node *next;

}node;

node *CreateList(node* head, char d);

void display(node *head);

int comparelistString(node *list1, node *list2);

int main()

{

    node *list1  = NULL;

    node *list2 =  NULL;

    list1 = CreateList(list1,'g');

    CreateList(list1,'e');

    CreateList(list1,'e');

    CreateList(list1,'k');

    CreateList(list1,'s');

    CreateList(list1,'d');

     list2 = CreateList(list2,'g');

     CreateList(list2,'e');

     CreateList(list2,'e');

     CreateList(list2,'k');

     CreateList(list2,'s');

     CreateList(list2,'c');

    cout<<"Elements in List 1:-"<<endl;

    display(list1);

    cout<<"\n\nElements in List 2:-"<<endl;

    display(list2);

    cout<<endl;

    cout<<"\n\ncomparison Result of String is ::  "<<comparelistString(list1, list2)<<"\n\n";

    return 0;

}

void display(node *head)

{

    while(head!=NULL)

    {

        cout<<head->data<<" ";

        head=head->next;

    }

}

node *CreateList(node* head, char d)

{

    node *ptr;

    ptr = head;

    if(ptr==NULL)

    {

        ptr = new node;

        ptr->data = d;

        ptr->next = head;

        head= ptr;

    }

    else

    {

        while(head->next!=NULL)

        {

            head= head->next;

        }

        head->next = new node;

        head= head->next;

        head->data =d;

        head->next = NULL;

    }

}

int comparelistString(node *list1, node *list2)

{

    while(list1 !=NULL && list2 !=NULL &&(list1->data == list2->data))

    {

        list1 = list1->next;

        list2 = list2->next;

    }

    if(list1!=NULL && list2!=NULL)

        return((list1->data > list2->data)?1: -1);

    if(list1!=NULL && list2==NULL)

        return 1;

    if (list1==NULL && list2!=NULL)

        return -1;

    return 0;

}

Output

Output

Refer link for more details

Other Articles:

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

Other Blogs: Click here

Find merge point of two linked list

Find merge point of two linked list

Find merge point of two linked list

#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *next;
}node;

int find_count(node *head);
int Get_insection_point(int , node*, node*);
int Get_insection_node(node*, node*);
void display(node* ptr);

int main()
{
   node* newNode;
   node* head1 =
            ( node*) malloc(sizeof( node));
  head1->data  = 10;

   node* head2 =
            ( node*) malloc(sizeof( node));
  head2->data  = 3;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 6;
  head2->next = newNode;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 9;
  head2->next->next = newNode;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 15;
  head1->next = newNode;
  head2->next->next->next  = newNode;

  newNode = ( node*) malloc (sizeof( node));
  newNode->data = 30;
  head1->next->next= newNode;

  head1->next->next->next = NULL;



        cout<<"Elements in List 1 "<<endl<<endl;
        display(head1);
        cout<<endl;
        cout<<"Elements in List 2 "<<endl<<endl;
        display(head2);

        cout<<"\n\n Insection node is:- "<<Get_insection_node(head1,head2)<<endl<<endl;
        return 0;
}

void display(node* ptr)
{
    while(ptr!=NULL)
    {
        cout<<ptr->data<< " ";
        ptr=ptr->next;
    }
    cout<<endl<<endl;
}

node* create_list(node* head, int item)
{
    node* ptr = head;
    if(ptr ==NULL)
    {
        ptr = (node*)malloc(sizeof(node));
        ptr->data = item;
        ptr->next = NULL;
        head =ptr;
    }
    else
    {
        while(ptr->next!=NULL)
        {
            ptr= ptr->next;
        }
        ptr->next = (node*)malloc(sizeof(node));
        ptr= ptr->next;
        ptr->data = item;
        ptr->next = NULL;
    }
return ptr;
}

int find_count(node *head)
{
    int count1=0;
    while(head!=NULL)
    {
        count1++;
        head=head->next;
    }
    return count1;
}

int Get_insection_node(node* head1, node* head2)
{
    node * node1Ptr = head1;
    node* node2Ptr = head2;
    int d=0;
    int countC1 = find_count(node1Ptr);
    cout<<"no of elements in List 1 :-"<<countC1<<endl;
    int countC2 = find_count(node2Ptr);
    cout<<"no of elements in List 2 :-"<<countC2<<endl;
    if(countC1>countC2)
    {
        d = countC1-countC2;
        return Get_insection_point(d,node1Ptr,node2Ptr );
    }
    else
    {
        d= countC2-countC1;
        return Get_insection_point(d,node2Ptr,node1Ptr );
    }
}

int Get_insection_point(int d , node* head1, node* head2)
{
     node * node1Ptr = head1;
    node* node2Ptr = head2;

    for(int i=0;i<d;i++)
    {
        if(node1Ptr==NULL)
        {
            return -1;
        }
        node1Ptr = node1Ptr->next;
    }

    while(node1Ptr!=NULL && node2Ptr!=NULL)
    {

        if(node1Ptr->data == node2Ptr->data)
            return node1Ptr->data;
        node1Ptr = node1Ptr->next;
        node2Ptr = node2Ptr->next;
    }
    return -1;
}

Merge Two link List( 1: Normal Approach 2: Recursion Approach)

Merge Two link List( 1; Normal Approach 2: Recursion Approach)

Merge-Link-list

#include <stdio.h>

#include<stdlib.h>

using namespace std;

// defining structure for the link list

typedef struct node_list

{

    int data;

    struct node_list *next;

} node;

/* functions*/

node * Merge_list(node *x, node*y);

void display(node *n);

node *create_list();

node *create_list(node *ptr, int item)

{

    node *temp ;

    if(ptr==NULL)

    {

        ;

        temp = (node*)malloc(sizeof(node));

        temp->data = item;

        temp->next = ptr;

        ptr = temp;

    }

    else

    {

        while(ptr->next!=NULL)

           ptr= ptr->next;

        ptr->next = (node*)malloc(sizeof(node));

        ptr= ptr->next;

        ptr->data = item;

        ptr->next = NULL;

    }

return ptr;

}

node *Merge_list(node *x, node*y)

{

    if(x==NULL)

        return y;

    if(y==NULL)

        return x;

    node *t = x;

    node *ptr = x;

    x= x->next;

    while(x!=NULL && y!=NULL)

    {

        t->next = y;

        y = y->next;

        t = t->next;

        t->next = x;

        x= x->next;

        t=t->next;

    }

    if(x!=NULL)

        t->next = x;

    else if(y!=NULL)

        t->next = y;

    else

        t->next = NULL;

    return ptr;

}

void display(node *ptr)

{  int i=0;

    while(ptr!=NULL)

    {

        cout<<ptr->data<<"->";

        ptr= ptr->next;

    }

}

/*using recurison*/

node* sort_merge_list(node* a, node *b)

{

    if(a==NULL)

        return b;

    if(b==NULL)

        return b;

    node* res = NULL;

    if(a->data <=b->data)

    {

        res = a;

        res->next = sort_merge_list(a->next,b);

    }

    else

    {

        res =b;

        res->next = sort_merge_list(a, b->next);

    }

    return res;

}

int main()

{

    node* list1 = NULL;

    list1 =  create_list(list1, 1);

    for(int i=2;i<10/2;i++)

    create_list(list1, i);

    display(list1);

    cout<<endl;

    node* list2 = NULL;

    list2 =  create_list(list2, 5);

    for(int i=11;i<30/2;i++)

      create_list(list2, i);

    display(list2);

    node* Mergelist = sort_merge_list(list1, list2);

    cout<<endl;

    display(Mergelist);

    cout<<endl;

    return 0;

}