CareerCup

Use the QuickSelect algorithm (look it up at Wiki, (O(N) time complexity)) for the randomly distributed elements in the matrix or, if the columns and rows are sorted, do an in-place merge in O(N) time of columns (or rows) and just return the element at index "k".

Algo:
1) use min_heap for inserting the indexes of matrix starting from (0,0)
2) keep count of numbers extracted
3) push indexes which are not yet in the heap in loop.
4) exit once count is == k

pseudo code:

find_kth_element(unsigned a[][], unsigned k)
{
    unsigned count=0;
    unsigned row, col;
     push(0,0);
    while(count != k) {
      point p = extract_min();
     count++;
     //now push neighbor index of p.x and p.y into heap 
    }
}

Note: I saw this solution somewhere in the web.

This is a O(k logk) solution written in c++

#include <cstdio>
#include <queue>
#include <cstdlib>
#include <climits>

using namespace std ;

#define SIZE 4

int matrix[SIZE][SIZE] = {
  {1, 2, 6, 10},
  {3, 4, 7, 13},
  {5, 9, 11, 14},
  {8, 12, 15, 16} 
};

typedef struct node {
  int x, y ;
  int val ;
  bool operator < (const node& obj) const {
    return (val > obj.val) ;
  }
}node ;

int findKthMin (int mat[SIZE][SIZE], int k) {
  int count = 0 ;
  node n ;
  int row, col ;
  priority_queue <node> elements ;
  n.x = 0 ; n.y = 0 ; n.val = mat[0][0] ;
  mat[0][0] = INT_MAX ;
  elements.push (n) ;

  while (count <= k) {
    n = elements.top() ;
    elements.pop () ;
    printf ( "%d\n", n.val ) ;
    count ++ ;
    node temp ;

    if ( n.x < SIZE-1 ) {
      temp.x = n.x + 1 ;
      temp.y = n.y ;
      if ( mat[temp.x][temp.y] != INT_MAX ) {
        temp.val = mat[temp.x][temp.y] ;
        mat[temp.x][temp.y] = INT_MAX ;
        elements.push (temp) ;
      }
    } 
    if ( n.y < SIZE-1 ) {
      temp.x = n.x ;
      temp.y = n.y + 1 ;
      if ( mat[temp.x][temp.y] != INT_MAX ) {
        temp.val = mat[temp.x][temp.y] ;
        mat[temp.x][temp.y] = INT_MAX ;
        elements.push ( temp ) ;
      }
    }
  }
}

int main () {
  int k ;
  printf ( "\nEnter the k (0 index) :\t" ) ;
  scanf ( "%d", &k ) ;
  findKthMin (matrix, k) ;
  return 0 ;
}

If space is not an issue.... We can copy the matix into a sorted one-dim array and 
after that, use the following code:

#include<stdio.h>

int main()
{
    int a[20];
    int num,k,i,c;
    printf("Enter number of elements\n");
    scanf("%d",&num);
    printf("Enter elements\n");
    for(i=0;i<num;i++)
    {
                 scanf("%d",&a[i]);           
    } 
    printf("Enter k\n");
    scanf("%d",&k);
    c=1;
    for(i=1;i<num;i++)
    {
                      if(c==k)
                      {
                              printf("kth Smallest with k=%d is %d",k,a[i-1]);
                              break;
                      }
                      if(a[i]!=a[i-1])
                              c++;
    }
	scanf("%d",&i);
	return 0;  
}

The rows and columns of the matrix are sorted. example
2 5 6
5 7 9
6 8 10

Suppose int arr[n][m] is an array
steps
=========
1) sort all rows in ascending order .
2) Then sort all columns in ascending order .
3) now

int kthsmallest;
for(int i=0;i<n;i++)
{
     for(int j=0;j<m;j++)
     {
          if( (i*m+j) == k ) 
          {
              kthsmallest arr[i][j];
          } 
     }
}

@ Neetesh Bhardwaj :
wht is k here...??

int find_n(int x[][3],int row, int col, int n) {

int r =0 , c = col -1;
while( r < row && col >=0) {
if(x[r][c] == n)
return n;
else if ( x[r][c] > n)
c--;
else
r++;
}
return -1;
}

public class MatrixKthelement {

public static void main(String str[]) {
int a[][] = { { 1, 13, 15 }, { 19, 20, 4 }, { 6, 7, 5 } };

int ele = 5;

int biggest = 0;
boolean found=false;
int countl=0;


for(int l=3-1;l>=0;l--){

for(int k=3-1;k>=0;k--)
{

biggest = a[l][k];
int posSmallX=l;
int posSmally=k;


for(int i=0;i<l+1;i++){

int lim;
if(i==l)
lim=k;
else
lim=3;
for(int j=0;j<lim;j++){
if(a[i][j]>biggest){
biggest=a[i][j];
posSmallX=i;
posSmally=j;
}
}
}

{

int temp=a[l][k];
a[l][k]=biggest;
a[posSmallX][posSmally]=temp;
countl++;
if(countl==ele){
System.out.println("the kth element is"+biggest);
found=true;
break;
}
}
if(found)break;
}



if(found)break;

}


}
}

Quickselect(int a[][],int row,int column,int k)
{
int *p = (int*)a;
do quickselect() on elements of p[row*column] //consider p as single dim array
//quickselect() is discussed many times on this forum
}

class FindKthSmallestInMNMatrix
    {
        int[][] matrix;

        public FindKthSmallestInMNMatrix(int M, int N)
        {
            matrix = new int[M][];

            for (int i = 0; i < matrix.Length; i++)
            {
                matrix[i] = new int[N]; 
            }

            Random random = new Random();
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    matrix[i][j] = random.Next(100);
                }
            }
        }

        public int Solve(int k)
        {
            if(k < 1 || k > matrix.Length * matrix[0].Length) 
            {
                return -1;
            }

            // allocate an array of M x N size to hold distinguished elements sorted in increasing order
            int[] array = new int[matrix.Length * matrix[0].Length];

            // init array with max int elements
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = int.MaxValue;
            }

            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    // check if matrix element already exists in array and find the correct place to insert further
                    bool exists = false;
                    int place = -1;
                    for (int a = 0; a < array.Length; a++)
                    {
                        if (matrix[i][j] == array[a])
                        {
                            exists = true;
                        }
                        else if (matrix[i][j] < array[a] && place == -1)
                        {
                            place = a;
                        }
                    }

                    if (!exists)
                    {
                        // shift the existing elements greater than the new element
                        for (int y = array.Length - 1; y > place; y--)
                        {
                            array[y] = array[y - 1];
                        }

                        // insert the new element
                        array[place] = matrix[i][j];
                    }
                }
            }

            return array[k - 1];
        }
    }

Why so complicated, guys?
QuickSelect would be the best solution, yeah, but that's the kind of thing I'd stick to a library function for. Remember, these are interview questions; keep it simple.
QS would be O(m*n), but wtherwise, you'll be running O((m*n)^2) anyways (such as in the solutions above), so why complicate things further?
The simple solution:

int mins[4];
int swap;
int currVal;

for(int i=0; i<k; i++) {
	mins[i] = INT_MAX;
}

for(int idx_m = 0; idx_m < m; idx_m++) {
	for(int idx_n = 0; idx_n < n; idx_n++) {
		currVal = matrix[idx_m][idx_n];
		swap = 0;
		for(int idx=0; idx < k; idx++) {
			if(currVal < mins[idx]) {
				swap = mins[idx];
				mins[idx] = currVal;
				currVal = swap;
			}
		}
	}
}

return mins[k-1];
// If INT_MAX is returned, there are fewer than k unique elements in the matrix

I have one sol :- (plz correct me if i am wrong )
make a BST and then take a inorder traversal in array .. then simply print kth element.
Note :- we have to keep track of index numbers also.

import java.io.*;
import java.util.*;
public class Kth_smallest_in_Matrix {
public static int find_min(TreeSet s,int k)
{
   Iterator l = s.iterator();
   int i=1;
   System.out.println("\n");
   while(l.hasNext())
   {   int h =(int)l.next();
	   System.out.print("   "+h);
	   if(i==k)
		   return h;
	   i++;
    }
   return -1;
}
public static int addtomatrix(int[][] a, int k,int r,int c)
{
	TreeSet t = new TreeSet();
	for(int i=0;i<=r-1;i++)
	{
		for(int j =0;j<=c-1;j++)
		{
			t.add(a[i][j]);
		}
	}
	
	return find_min(t,k);
}
public static void main(String[] args)
{
	int r = 2;
	int c = 3;
	Random ran = new Random();
	int[][] a = new int[r][c];
	for(int i=0;i<=r-1;i++)
	{
		for(int j=0;j<=c-1;j++)
		{
		  a[i][j]=ran.nextInt(100);
		  System.out.print(a[i][j] +"  ");
		}
		System.out.println();
	}
	System.out.print("\n\n"+addtomatrix(a,3,r,c));
}
}

The Treeset datastructure provides the sorted storage and would only allow unique elements .and have very effecient insertion times which is constant ..

Use max_heap of size k.
Scan upto k elements of the matrix & insert in the max heap.
Now, for each new element of matrix, check whether if it is smaller than the head of the heap.
If it is smaller, replace the head element with this new element. Update the heap.
At last, The head denotes the kth smallest element.
Time complexity: O(M*N*log(k))
Space complexity: K

Let me know if i am missing anything.

Cracked it!!
Sometimes, we use to think too much. However, we already know the solution.
Modified partition algorithm of quick sort solves the problem in O(MxN) time& without using any extra space.
here is the working code:

#define M 3  //number of rows
#define N 3  //number of columns

struct Index
{
	int row;
	int col;
}ind;

void swap(int *a,int *b)
{
	int temp=*a;
	*a=*b;
	*b=temp;
}

void partition(int (*A)[N],int lr,int lc,int hr,int hc)
{
	int pivot=A[lr][lc],j,k,l,m;
	j=hr;k=hc;
	l=(lc==N-1)?(lr+1):lr;
	m=(lc==N-1)?0:lc+1;

	while(1)
	{
		while(pivot>=A[l][m])
		{
			m++;
			if(m==hc && l==hr)
				break;
			if(m==N)
			{
				l++;
				m=0;
			}
		}

		while(pivot<A[j][k])
		{
			k--;
			if(k==lc && j==lr)
				break;
			if(k<0)
			{
				j--;
				k=N-1;
			}
		}

		if(l<j || (l==j && m<k))
			swap(&A[l][m],&A[j][k]);

		else
		{
			swap(&A[lr][lc],&A[j][k]);
			ind.row=j;
			ind.col=k;

			return;
		}
	}
}

void findkthSmallest(int (*A)[N],int lr,int lc,int hr,int hc,int k)
{
	int i;

	if((hc<N && hr<M) && (lr<hr || (lr==hr && lc<hc)))
	{
		partition(A,lr,lc,hr,hc);

		i=ind.row*N + ind.col;

		if(i+1==k)
		{
			printf("%d ",A[ind.row][ind.col]);
			return;
		}
		else if (i+1<k)
		{
			(ind.col==N-1)?(ind.col=0,ind.row++):(++ind.col);
			findkthSmallest(A,ind.row,ind.col,hr,hc,k);
		}
		else
		{
			(ind.col==0)?(ind.col=N-1,ind.row--):(--ind.col);
			findkthSmallest(A,lr,lc,ind.row,ind.col,k);
		}
	}
	else if(lr==hr && lc==hc)
	{
		i=lr*N + lc;
		if(i+1==k)
			printf("%d ",A[lr][lc]);
	}
}

Call : findkthSmallest(A,0,0,M-1,N-1,k); where A is the 2D Matrix.

Let me know your thoughts on this approach.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct index {
int x ;
int y ;
};
int a [5][5];

int partition ( int begin,int end ,int n, int m )
{
int i , p , q , temp;

int begin_x, begin_y,end_x,end_y ;
begin_x = begin/m;
begin_y = begin%m;
end_x = end/m;
end_y = end % m ;

int pivot = begin - 1;
int comp = a [ end/m ][end%m] ;
for ( i = begin ; i < end ; i ++ )
{
if ( a [ i/m ][i%m] < comp )
{
pivot ++ ;
temp = a [ i/m ][i%m] ;
a [ i/m ][i%m] = a [ pivot/m ][pivot%m] ;
a [ pivot/m ][pivot%m] = temp;
}

}
pivot ++ ;
temp = a [ end/m ][end%m] ;
a [ end/m ][end%m] = a [ pivot/m ][pivot%m] ;
a [ pivot/m ][pivot%m] = temp ;
return pivot ;
}

int quick_select ( int begin,int end , int k )
{
int n = end - begin ;
int pivot = partition (begin,end,4,4);
//cout << pivot << " " ;
//system("pause");
if ( pivot > (begin + k) )
return quick_select ( begin, pivot - 1 , k ) ;
if ( pivot == ( begin + k ) )
return pivot ;
if ( pivot < (begin +k) )
return quick_select ( pivot + 1 , end , k - pivot + begin - 1 ) ;
}

int main ()
{
for ( int i = 0 ; i < 4 ; i ++ )
{
for ( int j = 0 ; j < 4 ; j ++ )
cin >> a[ i ][j] ;
//cout << a[i] << endl ;
}

for ( int i = 0 ; i < 16 ; i ++ )
cout << "ans " << quick_select ( 0 , 15, i ) << endl;

for ( int i = 0 ; i < 4 ; i ++ )
{
for ( int j = 0 ; j < 4 ; j ++ )
//cin >> a[ i ][j] ;
cout << a[i][j] << " " ;
cout << endl ;
}
cout << endl << endl ;

system("pause");
}

What's this being a matrix have anything to do with the solution?

1. Algorithm cannot be less efficient than if the data was just a linear array. If linear array were more efficient, then just copy matrix into linear array.
2. Algorithm cannot be more efficient than if the data was just a linear array. If linear array were less efficient, then any linear array sorting problem would be speeded up putting it into a matrix which we know isn't the case.

Request to all. Please referain from writing code here. A algorithm is much more helpful.

I guess the question is challenging when we mention that the matrix is actually a "Young Tableau"
My proposed method destroys the array.
Pop the Minimum Value from the "Young Tableau" while maintaining the "Young Tabluea" property.
Each Pop can be done O(m+n) time
Hence to get k'th smallest, time would be O(k(m+n))
homeofcox-cs.blogspot.in/2010/04/young-tableau.html

Can someone tell a method which would not destroy the array