CareerCup

The best I can think of is k*log(k).

First of all, you only need to consider the left-top k*k matrix to find the k-th largest element. It's guaranteed to be in that smaller matrix. This helps especially when k << n.

Then extract the first element of each row and put it in the max-heap with size K. Building the heap takes time k*log(k).

Then remove the max element from the heap and put the next element in the same row into the heap. This step takes k*log(k) time.

So in total, 2k*log(k) = k*log(k) time.
It only requires O(k) space.

There may be better selection algorithm with better best-case performance. If you know of a better algorithm than mine, let me know!

- Junxian.Huang February 19, 2013 | Flag Reply

Everybody, why it's so hard? just a heap right?
Assume that we can pollute the array, then get the left-upper element, print it out, change it's value to be the max_int, then try to push it down to the heap.
method:
substitute it with the least immediate neighbor(the smaller between e(1,0) and e(0,1).).
continue to push the max_int down to the heap until no where to go.

Go back, get another minimum element at (0,0), repeat the same procedure, until you get the K-th minimum.

OK, this if for k-th minimum element, to get the k-th maximum, you need to do it in reversed direction. complexity will be k*log(max(m,n))

- Tony Guan March 05, 2011 | Flag Reply

I think the most straight forward method is to do a n-way merge sort and then get the k-th element out. To do in place, just use heap. we need to design the index strategy when doing this.

- xr February 05, 2013 | Flag Reply

Since the matrix is of the form of young tableau, we can call youngify(similar to heapify in case of heap) to find out the minimum element and then replace it with largest integer say Integer.MAX_VALUE. When we run this method k times, we will get the kth minimum element. {{{ // m and n are the dimensions of the matrix and i and j are initial positions will be send as 0,0. void youngify(int [][] a, int i, int j, int m, int n) { if(i > m || j > n) return; int x = -1, y =-1; if(i+1 < m && a[i][j] > a[i+1][j]) { a[i][j] = a[i+1][j]; x = i+1; y = j; } if(j+1 < n && a[i][j] > a[i][j+1]) { a[i][j] = a[i][j+1]; x = i; y = j+1; } if(x != -1) { a[x][y] = Integer.MAX_VALUE; youngify(a,x,y,m,n); } } - Manish Agarwal May 24, 2011 | Flag Reply

import heapq

def kth_mat(m, k):
  if k==0 or k>len(m)*len(m[0]):
    return "error"
  h=[(m[0][0], 0, 0)]
  for c in range(0, k):
    (v, x, y)=h[0]
    #print str(v)+" "+str((x,y))
    if y==0 and x+1<len(m):
      heapq.heappush(h, (m[x+1][0], x+1, 0))
    if y+1<len(m[0]):
      heapq.heapreplace(h, (m[x][y+1], x, y+1))
    else:
      heapq.heappop(h)
  return v

def main():
  m=[[1, 6, 10],[2, 7, 11], [3, 20, 30]]
  print m
  for k in range(1, len(m)*len(m[0])+1):
    print kth_mat(m, k)

- gen-y-s January 27, 2013 | Flag Reply

I can only think of O(k*lg(rownumber)) solution which just uses a heap to merge these arrays as rows.

- zyfo2 January 28, 2013 | Flag Reply

I just think it is merge sort. we can easily solve it through merge sort

- Anonymous January 30, 2013 | Flag Reply

This can be done using the method as follows:
1.take an array of sqrt(n)(assuming n is the total # of elements): int[] arr=new arr[sqrt(n)]
2.initially fill it with all the elements of array with the last element of each row
i.e for each x in arr do x=last element of each row in matrix
3.now take int largest=findLargest(arr) where findLargest(arr) computes largest element in the array(this can be done using a max heap and takes O(log(sqrt(N))) and replace the largest element in that array with its previous element in the matrix(i.e if its a[i][j] ,replace it with a[i][j-1])
4.now repeat step 3 "k" times..which gives the Kth Largest element
Time Complexity: O(k*log(sqrt(n)))

- Karthik Vvs February 02, 2013 | Flag Reply

In place means O(1) space I presume.

"Most efficient" would probably be too much for an interview (even the "most efficient" {say, asymptotic run time in RAM model} with no space restrictions is a hard problem).

Why do people even put that in the question? Only idiotic interviewers will be looking for the vaguely defined "most efficient" algorithm etc. More likely scenario is that the interviewer might have asked a simple question "can you improve it (some objective metric)?", which the interviewee interprets as asking for most efficient/best etc. Highly annoying.


As to the original problem: a simple idea is store the current r^th maximum. And use that to try and find that (r+1)^th. We can restrict ourselves to the k by k submatrix, this gives an O(k^3) algorithm.

- Anonymous February 04, 2013 | Flag Reply

It is surprised to me why no one has tried the BFS-like method. My logic will be like this:
(1)use a priority queue to store the frontiers, initiated with [0][0] or [N-1][N-1] depends on the input is as- or de-scending sorted.
(2) count the numbers cnt been dequed

for cnt < k:
deq- the priority queue and enq- its closed neighbors

I am not an expert on the time/space complexity analysis, but I believe it is efficient this way to my intuitive. :P

- Frank Wang November 14, 2014 | Flag Reply

I can think of a worst case scenario, a kth element has to be in the first root(K) (rows + columns) i.e. rootk(2n-rootk) elements
For example, a 9th element in a 10x10 matrix should be in the first 3 rows and 3 columns. i.e. 9th element is in these 51 elements.
complexity using this would be, sorting rootk(2n-rootk) elements, O(rootk(2n-rootk) * log(rootk(2n-rootk))) in the above example, O(51*log51)
space complexity O(rootk(2n-rootk))
thats the worst bound. better algorithms please.

- Synonymouse November 24, 2010 | Flag Reply

1> The smallest number is the one which doesn't have any number on the left or above.
2> (0,0) is the only one number which satisfies the rule no 1, so lets remove it and keep it as 1st smallest element.
3> Step 2, makes 2 element (0,1) & (1,0) to satisfy the rule no 1, find the smallest among them and remove it. It will release another one element to satisfy the rule no 1.
4> Repeat step 3 till you remove k element.

This is the same logic which can be used to sort the matrix in O(n).

- Mr Bean November 26, 2010 | Flag Reply

I think it's a heap.

- Anonymous November 29, 2010 | Flag Reply

int find_kth_largest (int A[][N])
{
	max_heap_t m_heap;
	std :: pair <int, int> next_largest;
	m_heap . insert (make_pair <int, int> (0, 0));
	int count = 0;
	
	while (1)
	{
		next_largest = m_heap . extract ();
		if (++count == k)
			break;

		m_heap . insert (make_pair <int, int> (next_largest -> first, next_largest -> second + 1));
		m_heap . insert (make_pair <int, int> (next_largest -> first + 1, next_largest -> second));
	}


	return A[next_largest -> first][next_largest -> second];
}

- Raghavendra Thodime December 19, 2010 | Flag Reply

Invariants
At any time there is atmost 1 element is in contention for the nth smallest no: representing a row and col
When an elt a[i][j] is less than kth smallest it leaves behind atmost 2 potential elts for the next smallest elt a[i+1][j],a[i][j+1]

struct/class pt{x,y}
boolean x_present[m]
boolean y_present[n]
Priority queue q
q.enqueue(pt(0,0))//Prioritizes values based on a[i][j]...minheap
while(k>0){
  pt(i,j)=q.removeMin()
  if(!x_present[i+1] && !y_present[j]){
    q.enqueue(pt(i+1,j))
    x_present[i+1]=true
    y_present[j]=true
  }
  if(!x_present[i] && !y_present[j+1]){
    q.enqueue(pt(i,j+1))
    x_present[i]=true
    y_present[j+1]=true
  }
    x_present[i]=false
    y_present[j]=false
  k--;
}
return a[i][j]

if u r using an array to implement priority queue max size required wud be s
where 1+2+3+4..+s is just greater than or equal to k

- Sathya February 14, 2011 | Flag Reply

Since the matrix is of the form of young tableau, we can call youngify(similar to heapify in case of heap) to find out the minimum element and then replace it with largest integer say Integer.MAX_VALUE. When we run this method k times, we will get the kth minimum element.

// m and n are the dimensions of the matrix and i and j are initial positions will be send as 0,0.

void youngify(int [][] a, int i, int j, int m, int n) {
     if(i > m || j > n) return;
     
     int x = -1, y =-1;
     if(i+1 < m && a[i][j] > a[i+1][j]) {
          a[i][j] = a[i+1][j];
          x = i+1;
          y = j;
     } 
     if(j+1 < n && a[i][j] > a[i][j+1]) {
          a[i][j] = a[i][j+1];
          x = i;
          y = j+1;
     }
     if(x != -1) {
          a[x][y] = Integer.MAX_VALUE;
          youngify(a,x,y,m,n);
     }
}

- Manish Agarwal May 24, 2011 | Flag Reply

A simpler version to follow: O(K log K) time, O(K) space
It uses a heap to find the next element, In the heap we put one item from each matrix row, and when an item is taken we push the next item to its right in the matrix.

import heapq

def first_k(m, k):
  if k==0 or k>len(m)*len(m[0]):
    return "error"
  h=[(m[0][0], 0, 0)]
  l=[]
  for c in range(0, k):
    (v, x, y)=heapq.heappop(h)
    l.append(v)
    if y==0 and x+1<len(m):
      heapq.heappush(h, (m[x+1][0], x+1, 0))
    if y+1<len(m[0]):
      heapq.heappush(h, (m[x][y+1], x, y+1))
  return l

def main():
  m=[[1, 6, 10],[2, 8, 12], [9, 11, 20]]
  print m
  print first_k(m, len(m)*len(m[0]))

- gen-y-s January 27, 2013 | Flag Reply

I could only found a link... This solves the problem in O(n) time

cse.yorku.ca/~andy/pubs/X%2BY.pdf

- googlybhai February 14, 2013 | Flag Reply

Well, we have sorted Matrix M*N.

int data[N][M] = ...;

The idea is to start sorting matrix using Megre Sort algo and stop when we find K-th element.
_____________________________________________
That's the interface for our class.

class IMegreSort2D 
{
	MegreSort2D(const int** data, int n, int m);
	int next(size_t count = 1);
};

We can use it such:

int k_sorted_element = MegreSort2D(data, N, M).next(k);

or such (to sort all matrix):

MegreSort2D sort(data, N, M);
for(int i=0; i<N*M; ++i)
	cout<<sort.next()<<endl;

_____________________________________________
Now we need to impliment function "next".

Let's create support structure Link. It will store position and value from this position. Also we will override operator< for them to compate 2 Link by values.

struct Link 
{
	int i, j;
	const T& value;
	Link(const int** data, int i, int j) : i(i), j(j), value(data[i][j]) {}	
	friend bool operator<(const Link& l1, const Link& l2) { return l1.value > l2.value; }
};

Of course, we can use str::pair<int,int> and get value from data. But, as for me, this version is more readable.
_____________________________________________
Now, our MergeSord need Min/Max Heap. In c++ we can use std::priority_queue.

priority_queue<Link> min_heap;

Firstly, we put there only smallest/biggest element:

min_heap.push(Link(data, 0,0));

Then, on each call 'next', we will take smallest/biggest element from this heap, and put next element from the same row to them:

int next()
{
	const Link& link  = min_heap.top(); //get smallest/biggest element from heap
	T value = link.value; //save to return
		
	if(link.i<(N-1)) //if it is not the last element of the row
		min_heap.push(Link(data, link.i+1,link.j)); //add next value from this row
		
	if(link.i==0 && link.j<(M-1)) //if it was first element from the row
		min_heap.push(Link(data, 0,link.j+1)); //add first value from next row
		
	min_heap.pop();
	
	return value;
}

Also we put first element from the next row, when take first element from previouse row.

Here is full working code: ideone.com/xZqt51

- Darida October 28, 2013 | Flag Reply

void findKthLargestInSortedMatrix(int arr[N][N], int count)
{
	int n=N,i=N-1, j=N-1, row=N-1,col=N-1;
	if(count>n*n)
	{
		printf("\nNot Enough elements");
		return;
	}
	printf("\n%dth largest element is:", count); 
	while( count>1 )
	{
		count--;
		if(arr[i-1][j] < arr[i][j-1])
			j--;
		else
			i--;
		if(i<0)
		{
			j--;
			i=row;
			col--;
		}

		if(j<0)
		{
			i--;
			j=col;
			row--;
		}
	}
	printf(" %d", arr[i][j]);
}

- AgentMac March 10, 2014 | Flag Reply

It can be O(n), where n = floor(sqrt(K))
Key point: n^2 <= K and K <= (n+1)^2
Proof: by definition of floor(): we have n <= sqrt(K) <= n+1, Q.E.D.
So for the bottom right nxn matrix, all elements are larger than what we are looking for, or it is the element at the left top corner.
Then we need only to examine two 1xn matrix at the left and top to the nxn matrix.
Since both are sorted already, it takes linear time to find the one we want: (K-n^2)th largest.

O(sqrt(K)) time, O(1) space.

Just my two cents

- Kamarkaka June 25, 2014 | Flag Reply

public static int KthMaxSortedMartix(int k, int n, int[,] dataArray)
        {
            int res = -1;
            int[] maxIndexex = new int[k];
            for (int i = 0; i < k; ++i)
            {
                maxIndexex[i] = n - 1;
            }
            for (int i = 0; i < k; ++i)
            {
                int max = int.MinValue;
                int maxIndex = 0;
                for (int j = 0; j < k; ++j)
                {
                    if(dataArray[n-j-1, maxIndexex[j]] > max)
                    {
                        maxIndex = j;
                        max = dataArray[n-j-1, maxIndexex[j]];
                    }
                }

                maxIndexex[maxIndex]--;
                res = max;
            }

            return res;
        }

- hatiger July 28, 2014 | Flag Reply

As the matrix is sorted by rows and columns, take any element, its top and left element will be less than the element and right and bottom element will be greater than the element. lets assume the element is a. If a is removed from the matrix, we will check left and top. Let us assume left is greater than top. If we put left in place of a,
left<a and a<right => left<right, which maintains the row wise sorting.
as a > left, bottom > a => bottom > left
and we already assumed that left>top
So these two equation proves that column wise sorting is also maintained. Similar equations will arise if top is greater than left and we replace the vacant place with top. So we can replace the removed element with the greater of top and left. and then continue the process to the next removed place till there is nothing more to remove. So this rearrange occurs in an N*M matrix in O(N+M) complexity.

Now to solve the original problem we just remove the right, bottom element k times and rearrange after every removal. As the right, bottom element is highest in the matrix, after removing k-1 times we can find the kth largest element in that position.
The total complexity will become O(K(M+N))
In an N*N matrix it is O(K(2N)) = O(KN)

Code

public class KthLargestSortedMatrix
{
 public static void main(String[] args)
 {
  int[][] matrix =
  {
  { 5, 7, 8, 9 },
  { 6, 9, 10, 13 },
  { 7, 11, 12, 15 },
  { 8, 13, 16, 17 } };
  int result = findKthLargest(matrix, 8);
  System.out.println(result);
 }

 private static int findKthLargest(int[][] matrix, int k)
 {
  for (int i = 0; i < k - 1; ++i)
   reArrange(matrix, matrix.length - 1, matrix[0].length - 1);
  return matrix[matrix.length - 1][matrix[0].length - 1];
 }

 private static void reArrange(int[][] matrix, int row, int col)
 {
  int newRow = 0;
  int newCol = 0;
  if (row == 0 && col == 0)
  {
   matrix[row][col] = Integer.MIN_VALUE;
   return;
  } else if (row == 0)
  {
   newRow = row;
   newCol = col - 1;
  } else if (col == 0)
  {
   newRow = row - 1;
   newCol = col;
  } else if (matrix[row][col - 1] > matrix[row - 1][col])
  {
   newRow = row;
   newCol = col - 1;
  } else
  {
   newRow = row - 1;
   newCol = col;
  }
  matrix[row][col] = matrix[newRow][newCol];
  reArrange(matrix, newRow, newCol);
 }

}

- Vivek October 08, 2014 | Flag Reply

Is the last column in first row lesser then dfirst element in second row ?

- Anonymous January 10, 2015 | Flag Reply

k can range from 1 to n^2 th largest element. deriving a solution that is in o(k) or o(k log k) would be o(n^2) in the worst case.

instead

we know that any element below any diagonal is less than the diagonal elements and similarly elements above it are all greater.

main procedure

step - 1: calculate the elements above or below the main diagonal
triangle_count = n(n-1)/2

step - 2: determine if k <= triangle_count, if so process only elements below the main diagonal
process_triangle(below_main_diagonal, n-1)

step - 2: else if k > triangle_count + n (there are n main diagonal elements), process only elements above the main diagonal
process_triangle(above_main_diagonal, n-1)

step - 3: else heapify the main diagonal and find (k - triangle_count) th smallest/largest element

process_triangle ( below/above main diagonal, m)

/* m = n-1 initially (1 less than main diagonal) */

step - 1: calculate triangle_count = m(m-1)/2
step - 2: determine if k <= triangle_count,
process_triangle ( below_or_above_hypotenuse, m-1)
step - 3: else heapify the hypotenuse and find (k - triangle_count) th smallest/largest element

the procedure takes o(n) to determine the diagonal first
log n heap insert operations for the elements in the diagonal and
atmost n operations to find kth element in the diagonal (worst case)

so a total of (2n + log n) and hence running time is of o(n)

- ramyaa February 02, 2015 | Flag Reply

java code. Find approx sqrt of k and then add the element at that row and col index and all elements in right top and left bottom part of matrix to priority queue and poll it until you get the kth max element.

{{
int len = matrix.length;
int pos = (int)Math.pow(k, 0.5)-1;
PriorityQueue<Integer> pq = new PriorityQueue();
pq.add(matrix[pos][pos]);
for(int i = 0; i < pos; i++){
for(int j = pos+1; j < len; j++){
pq.add(matrix[i][j]);
pq.add(matrix[j][i]);
}
}
int currentEl = -1;
int piv = (int)Math.pow(pos+1, 2);
while(piv <= k){
currentEl = pq.poll();
piv++;
}
System.out.println(currentEl);
}}

- turukmakto1990 December 19, 2016 | Flag Reply

Consider a simple matrix like this one:

1 3 5
2 4 6
7 8 9


You can solve this problem in O(k log n) time by merging the rows incrementally, augmented with a heap to efficiently find the minimum element.

Basically, you put the elements of the first column into a heap and track the row they came from. At each step, you remove the minimum element from the heap and push the next element from the row it came from (if you reach the end of the row, then you don't push anything). Both removing the minimum and adding a new element cost O(log n). At the jth step, you remove the jth smallest element, so after k steps you are done for a total cost of O(k log n) operations (where n is the number of rows in the matrix).

For the matrix above, you initially start with 1,2,7 in the heap. You remove 1 and add 3 (since the first row is 1 3 5) to get 2,3,7. You remove 2 and add 4 to get 3,4,7. Remove 3 and add 5 to get 4,5,7. Remove 4 and add 6 to get 5,6,7. Note that we are removing the elements in the globally sorted order. You can see that continuing this process will yield the kth smallest element after k iterations.

(If the matrix has more rows than columns, then operate on the columns instead to reduce the running time.)

- harrypotter0 September 22, 2017 | Flag Reply

start from largest element - a[n][n]
traverse back K elements, each "traverse" requires at most 5 comparisons-O(1)
O(k)

- Anonymous November 24, 2010 | Flag Reply

#!/usr/bin/ruby
#
# Given a N*N Matrix. 
#	All rows are sorted, and all columns are sorted.
#	Find the Kth Largest element of the matrix.

m = [ [1,6,9 ],
	  [3,7,10],
	  [5,8,11] ]

n = m.length

k = 1
large = 0

# Find the size of the sub matrix that we are going to be using
# to find the kth largest element. so for k = 5, we need to look
# at a matrix of size 2 x 2. This matrix is the above 'm' excluding
# the first row and first column
sub_n = Math.sqrt(k).ceil

# Convert the size of the sub matrix into a starting index into
# the original matrix m
start = n - sub_n

# We are going to be looking at only the first row and first column
# of the sub matrix as all other elements in the sub matrix are larger
# or equal to the elements of the first row and column of the sub matrix
# So reduce k by this amount
k = k - ((sub_n - 1) * (sub_n - 1))

def find_kth_largest(a1, a2, len, k)
	cur_large = 0
	a1_index = len - 1
	a2_index = len - 1
	while k != 0 do
		if a1[a1_index] > a2[a2_index]
			large = a1[a1_index]
			a1_index -= 1
		else
			large = a2[a2_index]
			a2_index -= 1
		end
		k -= 1
		if k == 0
			return large
		end
	end
end

# Extract the first row and first column of the sub matrix, and look for the k th
# largest element. The function above just uses the same algorithm a merging procedure
# in the merge sort uses. We start from the end, maintain 2 points to the current location
# from the end of the row and column extracts and continuously go k times down either the
# row or the column till k is 0. Once k is 0, we know that we have the current element
# we went down as the kth largest element.
puts find_kth_largest(m[start][start..(n-1)], m[start..(n-1)].map{ |a| a[start] }, sub_n, k)

- Joel Fernandes November 24, 2010 | Flag Reply

For example, we have this 5x5 matrix

1 2 3 4 5
2 3 4 7 11
3 4 8 10 14
4 5 10 13 18
5 6 11 15 20

The elements in the matrix grow in diagonal order, i.e. elements in 3rd diagonal (3 3 3, from left up corner) will larger than elements of 2nd diagonal (2 2). So smallest item will be in left up corner, largest - in right bottom corner.

So task is devided into several subtasks:

1. we have to find the diagonal of the matrix, starting from right bottom corner, which uncludes K-th element. Let K = 5, so our diagonal is number 3 (11 13 14) as it includes 4th, 5th and 6th lagest elements.

2. sort found diagonal from lagest item to smallest. We got 14 13 11. As 2 diagonals N1 (20) and N2 (15 18) includes 3 items, than our item will be 2nd in sorted diagonal, i.e. 13.

- Anonymous November 24, 2010 | Flag Reply

what can be done is start from the max element i.e rightmost lowest.
1.push its neighbors into a max heap.
2.chose the max of this heap and include it into our move and then delete it from the heap.
3.also add its neighbors into the heap thereby maintaining the max property.
4.goto step 2 until we have done it for k times.

i hope this algo might work out.
complexity is is < nlogn.

- saumils1987 November 25, 2010 | Flag Reply

As onr more method, one can sort matrix, taking diagonal by diagonal begining from left top corner and then use insertion sort. Add each diagonal`s elements to array, sort it, take next diaagonal`s elements and sort again.

Theoretically, it would be O(N^3), but in fact matrix has elements growing in diagonal direction, so it can be rather fast. Space - O(N*N).

- Anonymous November 25, 2010 | Flag Reply

It waz asked in the 1st round phone interview!! And was asked to do inplace! heaps and data structs were not allowed!

- 646 November 25, 2010 | Flag Reply

find the current minimum, remove it. It opens one or two new contenders for minimum. The rule for one to be a new contender is it has to be the first in its row and first in its's column among the remaining elements.

1. Smallest number is (0,0) remove it. Now it opens (0,1) and (1,0)
2. Find the smallest of (0,1) and (1,0) and remove it. Assume we remove (0,1). Now (0,2) becomes the new contender to compare with the existing contenders. Now (1,0) and (0,2) will content with each other. Assume (0,2) is smaller and we remove it. Then it will give a new contender (0,3) to compare with (1,0). Assume (1,0) is smaller than (0,3). Then we remove (1,0) and new contenders (2,0) and (1,1) will come as both of them are first remaining in their rows and columns.
Do this till we remove the kth element

- Annonymous November 26, 2010 | Flag Reply

- pankaj November 30, 2010 | Flag Reply

A key thing to note here in reducing the number of elements in the NxN matrix is that index (i,j) in the matrix is greater than at least i*j - 1 elements. We can use this to constrain the set of elements we consider (by not considering elements that are greater than k elements)

Starting at (K,1), (floor(k/2), 2), (floor(k/3),3) ... (1,k) we have a boundary within which we consider elements (that are above or to the left of these elements). Going column wise, this gives us K + K/2 + K/3 + ... + K/K = K* (1 + 1/2 + 1/3 ... + 1/K) elements to consider.

The number (1 + 1/2 + 1/3 ... + 1/K) is the kth harmonic number which is bounded by log(k).

Thus we have K * log(K) elements to consider.

Sorting and finding the kth largest will take K * log(K) * log(K) time...

I'm sure there's a better algorithm.

- Arnab December 01, 2010 | Flag Reply

Here is the K*log(K) algorithm.

I had put an upper bound on the kth largest element in the last post by eliminating elements that were greater than k elements in the last post.

For every column in the matrix less than k (since columns greater than k have more than k values less than them), maintain an upper bound Ui of the elements that are considerable (Ui tracks the index, not the value).

Initially, Ui = K/i.

Next, we reduce this bound using a 'binary' search.

In every iteration, we do one of two things:

i. If we have greater than k elements over all the working sets, then find the maximum value out of all the upper bounds, ie,

m = Max(M[Ui, i]) for i = 1 to K,

Let the column be p.

Then set Up = Up/2 and continue on to the next iteration.

ii. If we have less than k elements, then find the minimum out of all the upper bounds.

min = Min(M[Ui, i]) for i = 1 to K

Let q be the column containing the minimum value.

Then Uq = Uq * 2.

Continue on to the next iteration.

In this way, at every iteration, we eliminate half the values in one column and do k comparisons.

The iterations end when we find the minimum value out of all the upper bounds and have exactly k elements in the working set (over all columns).

The running time (loose bound) is hence K*log(K).

- Arnab December 02, 2010 | Flag Reply

Hi, sorry for the naive question, but what's the definition of "the Kth Largest element of the matrix"? I'm not familiar with that.
Thanks!

- amojobim December 13, 2010 | Flag Reply

Well the naive algorithm is K^2 lg k. The kth largest should be within the kxk sub-matrix. So you just sort it and find out.

Dont know if this is the best or not, or whether I covered all cases, but here is a O(k^2) algorithm. Let's assume all elements in the array are unique, if not, this algorithm can be extended.

Start with k = 1, this is the minimum element in the array which is (0,0)
The key thing is that the second largest element can only be the immediate neighbors of (0,0). So it is either (1,0) or (0,1). Using this immediate neighbor approach, construct a list of nodes that you will "visit" next based on your selection of the k-1th element. Some python pseudo-code:

def add_if_not_exists(possibles, newt):
    if newt not in possibles:
        possibles.append(newt)

def find_next(arr, possibles):
    min = 9999999
    selx = 0
    sely = 0
    for (x,y) in possibles:
        if(arr[x][y] < min):
            min = arr[x][y]
            selx = x
            sely = y
    possibles.remove((selx,sely))
    if selx+1 < len(arr):
        add_if_not_exists(possibles, (selx+1,sely))
    if sely+1 < len(arr):
        add_if_not_exists(possibles, (selx,sely+1))
    return (selx,sely)

def find_kth(arr, k):
    possibles = [(0,0)]
    for idx in range(0,k):
        print idx
        (x,y) = find_next(arr, possibles)
        print (x,y)
        print arr[x][y]

At each stage this algorithm does < 2k comparisons. This comes from the fact that we only consider the immediate neighbor of the visited nodes and due to the sorted nature of the matrix, the selected nodes cannot form a "hole". I.e. you cannot select (0,0) (0,1) (0,2) (2,2) (1,0) (2,0) but not (1,1). Since there are k steps to reach to kth element, you are bounded by k^2.

PS: I know the holes are possible with the alg above if the matrix contains duplicate elements. That is why I said it can be improved to pick the min x and min y of all matches.

You can probably do some clever things where if k > N/2 then you go reverse (i.e. find the N-kth largest).

PPS: I just realized that I wrote the alg for finding the kth smallest element but you get the idea.

- Anonymous December 16, 2010 | Flag Reply

int find_kth_largest (int A[][N])
{
	max_heap_t m_heap;
	std :: pair <int, int> next_largest;
	m_heap . insert (make_pair <int, int> (0, 0));
	int count = 0;
	
	while (1)
	{
		next_largest = m_heap . extract ();
		if (++count == k)
			break;

		m_heap . insert (make_pair <int, int> (next_largest -> first, next_largest -> second + 1));
		m_heap . insert (make_pair <int, int> (next_largest -> first + 1, next_largest -> second));
	}


	return A[next_largest -> first][next_largest -> second];
}

- Anonymous December 19, 2010 | Flag Reply

Young Tableu is the best solution.
Algorithm runs in O( total_elements_in_array * max(row,column) )

- Jegan Shunmugavel December 19, 2010 | Flag Reply

suppose the matrix is visualized as a square lattice, and we color the largest k elements black. The colored structure has a shape of Young's tableau.

To find the (k-1)'th largest element, one only needs to check M uncolored elements in the vicinity of current colored structure. M is related to the linear length of the current colored structure

- nos December 19, 2010 | Flag Reply

O(k), in-place, no-extra data structure solution:

Initialization:
Use two pointers (row pointer and column pointer), both begin from the bottom-right corner of matrix (the maximum element).
Row pointer moves from bottom to top, and column pointer moves from right to left.

If the element pointed by row pointer is bigger than column pointer, row pointer moves to the next; else column pointer moves to the next.
If row pointer moves to the top (i.e. (0, Y), its next position will wrap inner-back (i.e. (preRow-1, Y-1)); if column pointer moves to the left-most (i.e. (X, 0)), it also moves back (i.e. (X-1, preCol-1));
Continue until count to k.

- wangbingold December 22, 2010 | Flag Reply

Instead of finding K-th largest element we can find the (N*N - K + 1)-th smallest element, so I will describe my approach how to find the K-th smallest element of matrix A.
Suppose 1 <= M <= N. It is easy to see that sub-matrix ([1,1] - [M,M]) contains the first smallest M*M elements. So, suppose that the sought K-th smallest element is located at [I,J]. Then we can say that all elements of sub-matrix ([1,1] - [M,M]), where M = max(I,J) - 1, are less than the sought element. the number M could be found by the following formula: M = [sqrt(K)]. In case when K = M*M, then the sought element is A[M,M]. Otherwise, it will be one of Line={A[M+1,1], A[M+1,2], ..., A[M+1,M+1]} or Column={A[1,M+1], A[2,M+1], ..., A[M,M+1]}. As we can see here are only (2*M + 1) elements and we must find the (L = K - M*M)-th element. Taking into account that Line and Column are sorted we can do it just using two pointers with L comparisons.
The overall time complexity is O(N) (exactly K-[sqrt(K)]*[sqrt(K)] comparisons, 2*N-2 in worst case when K=N*N-1) and O(1) memory.
Any comments are welcome :).

- fiddler.g January 05, 2011 | Flag Reply

I believe using a heap it can be solved in O(k*log k) time. The largest element is A[N,N]. 2nd largest is either A[N-1,N] or A[N,N-1]. So, for each element we add 2 elements in the heap. So the size of heap is bounded by O(k). Hence heapify() will take O(log k).

However, if heap is not allowed, I can get an O(k*N) solution. In this approach, every time a heapify() similar function is used to adjust the given Young Tableau matrix, which takes O(N) time.

Pls, try to find any possible flaw in my approaches. Thanks in advance.

- anonymous January 16, 2011 | Flag Reply

we in do it in O(MN)

set i,j,l=0
while(1)
{
if(l==k)
return a[i][j]
if(a[i][j+1]>a[i+1][j])
j++
else
i++
l++
if(i==m)
{
i=0
j++
}
if(j==n)
{
j=0
i++
}
}

- Anonymous January 21, 2011 | Flag Reply

This 2D array is a BST, rooted at upper-right corner.
So, In-order traversal of BST can out the kth smallest element. Complexity O(k).

- Anonymous February 12, 2011 | Flag Reply

Rows sorted ascending order
Columns sorted ascending order

1. Find 14-?
2. Find 13-?

1 2 3 4 5
6 7 8 9 10
11 12 14 15 16
17 18 19 20 21

->start from the last column of first row (which is 5)
->Go down that column until you hit a number which is greater than the search key
->traverse down the row until you either hit a number you wanted / lesser number than search key.
->return the result.

challenge is writing code. this question intention is that
-----------------------------------------------------------

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

int findIn2D(int searchKey, int **a, int m, int n)
{
    //->start from the last column of first row (which is 5)
    int p = 0;
    int q = n;

    //->Go down that column until you hit a number which is greater than the search key
    while(a[p][q] <= searchKey && p <= m)
    {
        if(a[p][q] == searchKey)
        {
            return 1;
        }

        //move row wise
        ++p;
    }

    //->traverse down the row until you either hit a number you wanted / lesser number than search key.
    if(p<=m)
    {
        while(a[p][q] >= searchKey && q >= 0)
        {
            if(a[p][q] == searchKey)
            {
                return 1;
            }

            //move row wise
            --q;
        }
    }
    return 0;
}




/*
 * 
 */
int main(int argc, char** argv) {

    int m = 4;
    int n = 5;
    int **a=(int **)malloc(m*sizeof(int *));
    
    for(int i=0;i<m;i++)
    {
        a[i]=(int *)malloc(n*sizeof(int));
    }
    
    int k = 1;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            k++; 
            if(k == 13)
            {
                k++;
            }            
            a[i][j]=k;
        }
    }

    if(findIn2D(13,a,m-1,n-1))
    {
        printf("Found \n");
    }
    else
    {
        printf("Not Found \n");
    }

    return 0;
}

- Anonymous February 12, 2011 | Flag Reply

I cant see how BST can be structured as mentioned in the previous solution.

Take example:

1 2 7 10 21
3 4 8 11 22
5 6 9 12 23
13 14 15 16 24

k = 12

step 1: rc = floor(sqrt(k));
So rc = 3
rc is the column/row in which the kth smallest element occurs.
So 10th smallest number occurs on the 3rd col or 3rd row. (columns start from zero)

step 2: p = k - rc^2;
so p = 3
p is the number of smallest elements in rc'th row/col to count before we hit the kth smallest element.


Step 3: Merge the elements of row rc and column rc to find the p'th smallest element.
We merge [10 11 12 16] and [13 14 15 16] and find 3rd smallest element which is 12.

If either row rc or col rc dont exist, no need to merge. If both of them dont exist, you have k > size of array.

Complexity is O(n) where n is the larger dimension of the 2d array

- vr February 12, 2011 | Flag Reply

void kthSmallest(int k, int **a, int m, int n)
{
//1 2 3 4 5
//6 7 8 9 10
//11 12 14 15 16
//17 18 19 20 21
// m = 4 and n = 5 and k = 21 or 13

assert(k <= (m*n));
assert(m!=0 && n!=0);

int q = n;
while(k>q && (q/n) <= m)
{
q = q + n;
}

int i = (q/n) - 1;
int j = n - (q-k) - 1;

printf("The element is: %d \n", a[i][j]);

}

- yogesh February 12, 2011 | Flag Reply

I can propose solution with modification of original array.
It is based on fact that smallest number is in left upper corner of the array and largest is in right bottom one. Let's take largest number equal to X. Algorithm takes first smallest number, replaces it with X+1 and then sorts given NxM array. This can be done with O(M+N) operations. As a result, smallest number will appear again in left top corner. Applying same operation k times will get k-th smallest element.
Complexity is O(k*(M+N)).

- Anonymous February 12, 2011 | Flag Reply

@everyone....please post your space and time complexity...

- Om Prakash Pl February 13, 2011 | Flag Reply

Given the rows(i) & columns(j) are already sorted. We need the kth smallest.Can't we do this-

1. Start from grid[0][j] -first row,last column.check if j==k then output j else goto step 2
2. if j<k then traverse that row (leftwards) till we get column number == k.
3. if j>k then consider grid[1][j]. repeat till we get k.

Complexity -
Space - O(1)
Time - O(i) + O(j) we are traversing each row. but going through column only once.

- srikar February 13, 2011 | Flag Reply

Similar question already asked by google
id=6335704

- Anonymous February 13, 2011 | Flag Reply

Use divide and conquer (sub division of array into pieces smaller than pivot grater than pivot). Initially choose pivot to be median array[n/2][m/2], the remaining pivots need to be selected in a randomized fashion (though it's easy to figure out media in the remaining array as well.

Analysis: T(nm) = T(nm/2) + O(n log m) depending on which one is bigger.

hence we have T(nm) = O((n log m)(log nm))

depending on n and m and k it might be better to use brute force search in some cases.

- nish February 13, 2011 | Flag Reply

Below programm written with following Basic Idea:
Take any size of sub-matrix from the input 2D matrix, the smallest element is left top one.

int r, c;	//	r:row,	c:column
int smallest[2][r*c];
int index = 0

int find_Kth_Min(int MAT[][], int r, int c, int kth_min)
{
	int i, j, k_x, k_y;
	
	if(kth_min == 0)
		return MAT[0][0];
	if(kth_min == r*c)
		return MAT[r][c];
	if(kth_min < 0 || kth_min > r*c)
	{
		printf("Invalid input");
		return;
	}

	for(i = 0; i<2; i++)
		for(j = 0; j<r+c; j++)
			smallest[i][j] = -1;
	//Keeping in index of smallest element
	smallest[0][0] = 0;
	smallest[1][0] = 0;
	index = 1;

	while(kth_min)
	{
		find_smallest(smallest, &k_x, &k_y, MAT);
		kth_min--;
	}
	return MAT[k_x][k_y];
}

void find_smallest(int smallest[][], int *k_x, int *k_y, int MAT[][])
{
	min = 9999999, p;
	for(int i=0; i<index; i++)
		if(MAT[smallest[0][i]][smallest[1][i]]<min)
		{
			min = MAT[smallest[0][i]][smallest[1][i]];
			*k_x = smallest[0][i];
			*k_y = smallest[1][i];
			p = i;
		}
	smallest[0][p] = k_x+1;
	smallest[1][p] = k_y;

	smallest[0][index] = k_x;
	smallest[1][index] = k_y+1;
	index++;
	return;
}

Time Complexity: O(K*3)

- SRB February 13, 2011 | Flag Reply

Assuming vals stored in a static array in consecutive memory locations,
m = number of rows.
n = no of columns.
k = kth smallest elem.


if ( k < 0 || k > m*n ) return INVALID_ARG;

int val = array[k/m][k%m];

'val', will be having the result.

Isn't this what we need ?

- B February 13, 2011 | Flag Reply

Starting with the bottom right element at matrix[n][n] which is the largest element (or n-1, but I'll use n for simplicity):
1. We know that elements in [n][n-1] and [n-1][n] are 2nd and 3rd largest elements (not respectively) - and these positions form a diagonal line immediately next to [n][n]
2. Similarly, elements in [n][n-2], [n-1][n-1] and [n-2][n] are 4~6th largest elements - again, these positions form a diagonal line immediately next to [n][n-1] and [n-1][n]
3. You can easily calculate which positions to search for, given k

I would order only the elements in a diagonal line and select a number at an appropriate position, e.g. if k=5, order elements in n][n-2], [n-1][n-1] and [n-2][n], and select the middle number.

- yy February 14, 2011 | Flag Reply

This array is a type of BST. We can do InOrder traversal. When we visit the k-th element, stop.

const int MAXINT=1000;

void InOrder(int x, int y, int low, int high)
{
	if ((x>=0) && (x<M) && (y>=0) && (y<N) && (array[x][y]<=high) && (array[x][y]>=low))
	{
		InOrder(x, y-1, low, array[x][y]);
		cout<<array[x][y]<<" ";
		count++;
		if (count==k) exit();
		InOrder(x+1, y, array[x][y], high);
	}
}

int main()
{
	init();
	InOrder(0, N-1, -MAXINT, MAXINT);
}

- Anonymous February 16, 2011 | Flag Reply

To yy:

Your approach is the same as mine:) Basically we start with the bottom-right point and walk towards the top-left. The first step gives the largest number a[n][n]; the second step gives the next two: a[n-1][n] and a[n][n-1] (don't know which is larger); then the third step would give the next three... Note that for any steps > n, the numbers it give would decrease instead, e.g. step n+1 gives n-1 numbers...

We can do a binary search (a speedup) to determine which step say x we would end up doing to locate the k-th largest element, this has O(logn) complexity. Then do a compare between all the numbers in the step x, at most n elements, and pick up the appropriate one, this at most takes O(n). So the total complexity would be O(n).

- fuzhijun2009 February 16, 2011 | Flag Reply

I tested the InOrder algo, seems at least some bug here:

3 3
1 2 5
2 3 6
3 4 7

InOrder:
1 2 2 2 3 3 3 4 5 6 7

- guanxiaohua March 05, 2011 | Flag Reply

The problem is very simple . We can solve the problem using binary search..The time complexity is O(n*log(a[n-1][n-1]-a[0][0])),n*n is the size of matrix and space complexity is O(1). I assume that the matrix contains no duplicate entries. In case duplicate entries are present small changes are required

I'm writing the code for finding the kth minimum . If you need to find kthmaximum just pass n*n-k+1.

/*Finding kth minimum in the matrix */
int a[100][100];
int n;
/*returns the number of elements which are smaller than or equal to x in the given matrix */
int f(int x){
int row=n-1,col=0;
int ct=0;
while(row>=0 && col<n){
   if(a[row][col]<=x)
      ct+=(row+1),col++;
   else
       row--;
}  
return ct;
}
int binary_search(int start,int end,const int &k){
   if(start>end) return a[n-1][n-1]+1;
   int mid = (start+end)>>1;
   int x = f(mid); 
  /* f(p) returns the number of elements which are smaller than or equal to
    p in the given matrix */
   if(x==k) return min(mid,binary_search(start,mid-1,k));
   else if(x>k) return binary_search(start,mid-1,k);
   else return binary_search(mid+1,end,k);

}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
       for(int j=0;j<n;j++)
         cin>>a[i][j];
    int k;
    
             cin>>k;
             cout<<binary_search(a[0][0],a[n-1][n-1],k)<<endl;
   
}

- madhav nasini March 13, 2011 | Flag Reply

Since the array is sorted, we know the largest number is matrix[m][m] and the next largest number is in either (m, m-1) or (m-1, m).

Let's say the 2nd largest number is at (m, m-1). And then we can know the 3rd largest number is in either (m-1, m), (m-1, m-1) or (m, m-2).

Let's say the 3rd largest number is at (m, m-2). And then we can know the 4th largest number is in either (m-1, m), (m-1, m-1) (m-1, m-2) (m, m-3).

so on and so on. If we keep this process going, we will be able to find the kth largest number is kth run and the time complexity is O(k*log k).

case class Item(value: Int, x: Int, y: Int) extends Ordered[Item] {
  override def compare(that: Item): Int = value - that.value
}

object YoungTableau {

  def findKthLargest(matrix: Array[Array[Int]], k: Int): Int = {
    val m = matrix.length - 1
    val n = matrix(0).length - 1

    val queue = new PriorityQueue[Item]()
    queue += new Item(matrix(m)(n), m, n)
    matrix(m)(n) = Int.MinValue

    for (i <- 1 until k) {
      val cur = queue.dequeue()

      val x = cur.x
      val y = cur.y
      val x1 = cur.x - 1
      val y1 = cur.y - 1

      if (x1 >= 0 && matrix(x1)(y) != Int.MinValue) {
        queue += new Item(matrix(x1)(y), x1, y)
        matrix(x1)(y) = Int.MinValue
      }

      if (y1 >= 0 && matrix(x)(y1) != Int.MinValue) {
        queue += new Item(matrix(x)(y1), x, y1)
        matrix(x)(y1) = Int.MinValue
      }
    }
    return queue.dequeue().value
  }
}

- yunglin May 16, 2012 | Flag Reply

public class Test
{
	public static void main(String[] args)
	{
		for(int i=1; i<= 9; i++)
		{
			int[][] array = new int[][] {
					{1,4,8},
					{3,70,80},
					{5,90,100}
			};
			
			findIt(array, i);
		}
	}

	public static void findIt(int[][] array, int largestK)
	{
		int smallest = -1;
		int smallestK = 0;
		for(int[] ar : array)
		{
			smallestK +=ar.length; 
		}
		smallestK -= (largestK-1);
		
		for(int i=0; i< smallestK; i++)
		{
			//Remove the first element
			smallest = array[0][0];
			removeTheSmallest(array, 0, 0);
		}
		System.out.println(smallest);
	}
	
	public static void removeTheSmallest(int[][] array, int i, int j)
	{
		if(array.length <= i+1 && array[i].length <= j+1)
		{
			return;
		}
		if(array.length <= i+1 && array[i].length > j+1)
		{
			array[i][j] = array[i][j+1];
			array[i][j+1]= Integer.MAX_VALUE;
			removeTheSmallest(array, i, j+1);
		}
		else if(array.length > i+1 && array[i].length <= j+1)
		{
			array[i][j] = array[i+1][j];
			array[i+1][j]= Integer.MAX_VALUE;
			removeTheSmallest(array, i+1, j);
		}
		else
		{
			if(array[i][j+1] < array[i+1][j])
			{
				array[i][j] = array[i][j+1];
				array[i][j+1] = Integer.MAX_VALUE;
				removeTheSmallest(array, i, j+1);
			}
			else
			{
				array[i][j] = array[i+1][j];
				array[i+1][j] = -1;
				removeTheSmallest(array, i+1, j);
			}
		}
	}
}

- Ted June 05, 2012 | Flag Reply

int [][] yT = {{1,3,5,7},{2,4,6,8},{3,5,7,9},{4,6,8,10}};
	int ROWS = 4;
	int COLS = 4;
	int HEAP_ROWS = 4;
	int HEAP_COLS = 4;
	public void maxYoungify(int x , int y){
		int smallest = yT[x][y];
		int x_new = x;
		int y_new = y;
		if( (x+1) < ROWS && smallest > yT[x+1][y]){
			smallest  = yT[x+1][y];
			x_new = x+1;
			y_new = y;
		}
		if( (y+1) < COLS && smallest > yT[x][y+1]){
			smallest  = yT[x][y+1];
			x_new = x;
			y_new = y+1;
		}
		if(x_new != x || y_new !=y ){
			yT[x_new][y_new] = yT[x][y];
			yT[x][y] = smallest;
			maxYoungify(x_new,y_new);
		}
	}
	
	public int kthElemenet(int k){
		int kValue = 0;
		for(int i = 0;i < k;i++){
			kValue = yT[0][0];
			yT[0][0] = Integer.MAX_VALUE;
			maxYoungify(0,0);
		}
		return kValue;
	}

- modi.osu August 25, 2012 | Flag Reply

hi
can you help me to write C++ program.
Consider a 4-by-4 array of characters. Write a C++ program to accomplish each of the following operations:
a. Declare the above array.
b. Read the array.
c. Find and print the number of zeros in both the diagonals of the array.
d. Replace each even number in the array by zero and then print the array as rows and columns.

- nahlala December 06, 2012 | Flag Reply

1st largest element is on the last diagonal. 2nd and 3rd largest element is on the 2nd diagonal. now find the diagonal for the k largest element. compare the elements of the diagonal to find the kth largest element. This is O(n^0.5) complexity.

- alex December 08, 2012 | Flag Reply

How is the matrix sorted. Example?

- Kamy January 27, 2013 | Flag Reply

1     2     3     25
        4    23    30     88
        7    82    90    100
        8    83    91    101
        
        k      1    2    3    4    5    6     7     8     9    10    11    12    13    14     15     16
        Ans    1    2    3    4    7    8    23    25    30    82    83    88    90    91    100    101
        
        Pseudocode to create a flat list
            Search through current row till subsequent row's current index content is bigger
            Update Index[current row] to last value seen
			
			From teh flat list return kth element
			
			
        For simplicity - assume all are 1-based index
		    rows = Number of rows in Matrix
		    cols = Number of cols in Matrix
		    Matrix[rows][cols] given    
		    Initialize Index[rows] as = { 1, 1, 1, 1 }
		    FlatSorted[rows*cols] = an array of rows * cols  elements that will be filled up
        
        
        int k = 1;
        for (int r=1; r<=rows; r++)
        {
            for (int current_row = 1; current_row <= rows; current_row++)
            {                
                if Index[current_row] < cols)
                {
                    int current_col = Index[current_row];
                    for (int next_row = current_row + 1; next_row <= rows; next_row++)
                    {
                        int next_col = Index[next_row];
                        if (next_col < cols and current_col < cols)
                        {
                            if (Matrix[next_row][next_col] >  Matrix[current_row][current_col])
                            {
                                FlatSorted[k++] = Matrix[current_row][current_col];
                                current_col++;
                            }
                            else
                            {
                                break;    // no need to look further at this current_row
                            }
                        }
                    }
                    Index[current_row] = current_col;
                }
            }
        }
        
        Walkthrough:
        
        Index[] = { 1, 1, 1, 1 }
        current row = 1    
            1    2    3
        Index[] = { 4, 1, 1, 1 }
        current row = 2
            4
        Index[] = { 4, 2, 1, 1 }
        current row = 3
            7
        Index[] = { 4, 2, 2, 1 }
        current row = 4
            8
        Index[] = { 4, 2, 2, 2 }

        current row = 1    
        Index[] = { 4, 2, 2, 2 }
        current row = 2
            23    
        Index[] = { 4, 3, 2, 2 }
        current row = 2
        Index[] = { 4, 3, 2, 2 }
        current row = 3
        Index[] = { 4, 3, 2, 2 }
        current row = 4
        Index[] = { 4, 3, 2, 2 }

        current row = 1
            25
        Index[] = { 5, 3, 2, 2 }
        current row = 2
            30
        Index[] = { 5, 4, 2, 2 }
        current row = 3
            82
        Index[] = { 5, 4, 3, 2 }
        current row = 4
            83
        Index[] = { 5, 4, 3, 3 }
        
        current row = 1
        Index[] = { 5, 3, 3, 3 }
        current row = 2
            88
        Index[] = { 5, 5, 3, 3 }
        current row = 3
            90
        Index[] = { 5, 5, 4, 3 }
        current row = 4
            91
        Index[] = { 5, 5, 4, 4 }
        
        current row = 1            
        Index[] = { 5, 5, 4, 4 }
        current row = 2
        Index[] = { 5, 5, 4, 4 }
        current row = 3            
            100
        Index[] = { 5, 5, 5, 4 }
        current row = 4
            101
        Index[] = { 5, 5, 5, 5 }

- sme January 27, 2013 | Flag Reply

Here is my correct working solution in python:
Assumed a square matrix, but the solution can be easily modified for a rectangular matrix.

def pushUp(m):
    i = j = len(m)-1
    n = m[i][j]
    while i > 0 and j > 0:
        if m[i-1][j] < n:
            if m[i][j-1] < n: return;
            else:
                m[i][j-1], m[i][j] = m[i][j], m[i][j-1]
                j -= 1
        else:
            if m[i][j-1] < n:
                m[i-1][j], m[i][j] = m[i][j], m[i-1][j]
                i -= 1
            else:
                x,y = i-1, j
                if m[i][j-1] > m[i-1][j]: x,y = i, j-1
                m[i][j], m[x][y] = m[x][y], m[i][j]
                i,j = x,y
            
        
if __name__ == "__main__":
    matrix = [[1,    2,     3,     25],
             [4,    23,    30,     88],
             [7,    82,    90,    100],
             [8,    83,    91,    101]]
    k = 7
    
    n = len(matrix)-1
    while k > 1:
        matrix[0][0], matrix[n][n] = - matrix[n][n], matrix[0][0]
        pushUp(matrix)
        k -= 1
    print matrix[n][n]

Very similar to extracting kth largest element from a max-heap.

- chisingh January 27, 2013 | Flag Reply

Why cant we do it like create an array of n*m element. And fill all the element of matrix into that and short the array in increasing order.
now we can find the Kth element.
Alas it wont be the efficient way...

- navin.pd January 27, 2013 | Flag Reply

/*# google-interview-questions 12 Answers

Given k, find the kth maximum element from a sorted matrix*/

#include<iostream>
#include<map>
using namespace std;


int arr[3][3]={10,20,30,40,50,60,80,90,110};

void FindKthElement(int arr[][3]){

map <int,int>myMap;
map <int,int>::iterator it;
int k=1;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){

if(!myMap.count(arr[i][j]))
myMap[k++]=arr[i][j];
}
}

//for(it=myMap.begin();it!=myMap.end();it++)
it=myMap.find(5);
cout<<it->second<<endl;



}

int main(){
cout<<"hello"<<endl;
FindKthElement(arr);
}

- Raj January 27, 2013 | Flag Reply

#include<stdio.h>
#include<stdlib.h>
int B[100];
int j=0;
int largest(int *p[],int n, int r, int *counter)
{
  int i;int max=*p[r];
  
  for(i=r+1;i<n;i++)
  {
    if(*(p[i])>max)
    {
      max=*p[i]; 
    }
  }
  for(i=0;i<n;i++)
  {
    if(max==*p[i])
    {
	  p[i]--;
     counter[i]++;
    }
  }
  return max;
}

int main()
{
  
int x[4][6]={{2,5,7,9,14,16}, 
             {3,6,8,10,15,21},
             {4,7,9,15,22,35}, 
             {7,8,9,22,40,58}};
  int m=4;//number of rows
  int n=6;//number of columns
  int *p[4]={x[3]+5,x[2]+5,x[1]+5,x[0]+5};//array of pointer storing each rows 
  int i,s=0;
  int counter[4];
  int r=0;
  int k=5;
  for(i=0;i<m;i++)
     counter[i]=0;
  int kth;
  while(s<k)
  {
    if(counter[r]==n)
       r--;
    kth=largest(p,m,r,counter);
   //printf("%d\n",kth);
    s++;
  }
    printf("%d\n",kth);
}

- Shashi January 27, 2013 | Flag Reply

When we have a sorted matrix, we move across the diagonal. The dth element in the diagonal is definitely greater than the square to the top-left of it.

For k, we need to have two consecutive diagonal elements d-1 and d, such that k lies in between the sizes of their top-left squares.

We are left with a sort of merge-sort-like comparision of the two arrays - horizontal and vertical of d.

- abyrupus January 28, 2013 | Flag Reply

How about this C# solution?
Complexity: O(N)

/* Algorithm
         * 
         * 1. Traverse through the matrix as if it were a simple one dimensional array. 
         * 2. Compare each element of the matrix to the previous one.
         *      If the elements are different, reduce k
         *      If k == 1, the current element is the kth largest element of the number.
         *      
         * 
         * Examples:
         * int[,] arr = null;           FindKthLargest(arr, 3);
         * 
         * int[,] arr1 = { { 1, 1, 1 }, 
         *                 { 4, 5, 6 }, 
         *                 { 7, 8, 9 } };
         *                 
         * int[,] arr2 = { { 1 }, 
         *                 { 4 }, 
         *                 { 7 } };
         *                 
         * int[,] arr3 = { { 1, 4, 7 } };
         * 
         * int[,] arr1 = { { 1, 1, 1 },
         *                 { 4, 5, 6 },
         *                 { 7, 8, 9 } };
         */
        public static void FindKthLargest(int[,] arr, int k)
        {
            if (arr == null)
                throw new ArgumentException("array cannot be null");

            int rows = arr.GetLength(0); //Get maximum number of rows.
            int cols = arr.GetLength(1); //Get maximum number of columns.

            if (k <= 0)
                throw new ArgumentException("K should be greater than 0");

            //If asked for first largest element, return the first element of the array
            if (k == 1)
            {
                Console.WriteLine("{0}st largest number is {1}", k, arr[0, 0]);
                return;
            }

            int temp = k; //will be decremented each time current element is different from the previous one.
            int prev = arr[0, 0];

            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    if (prev < arr[i, j])
                    {
                        temp--;
                    }
                    prev = arr[i, j];

                    if (temp == 1)
                    {
                        Console.WriteLine("{0}th largest number is {1}", k, arr[i,j]);
                        return;
                    }
                }
            }

            if (temp > 1)
                Console.WriteLine("{0}th largest number does not exist", k);
        }

- DrFrag January 31, 2013 | Flag Reply

A poly-line can be draw from bottom-left corner to top-right corner and separate the Matrix into two parts so that the upper-left one contain only values less than or equal to k and the other part contain values greater than k.
Only thing you need to do is to travel from bottom-left corner to top-right and figure out the separating poly-line, you'll find the k (if exist) along your path. The total complexity is O(rows+cols) since you traveled this far.

- cff29546 February 01, 2013 | Flag Reply

public int[] merge (int[] a,int[] b)
{
	int n =  a.length;
	int m =  b.length;
	
	int[] c = new int[m+n];
	
	int p=0,q=0;
	
	while(p<n && q<m)
	{
		if(a[p] < b[q])
			c[p+q] = a[p++];
		else
			c[p+q] = b[q++];
		
	}
	
	if (p>=n)
	{
		while (q<m)
			c[p+q] = b[q++];
	}
	
	else	
	{
		while (p<n)
			c[p+q]= a[p++];
	}
	
	return c;
	
  }


public int kthlargest(int[][] a,int n,int k)
{
	
	//searching based on the fact that diagonal elements are 1st,4th,9th largest elements in the array
	
	//if k is perfect square, this runs in O(1), assuming no numbers repeat
	
	int sqr = (int) Math.sqrt(k);
	if(k == sqr * sqr)
		return a[n-sqr][n-sqr];
	
	// finding the closest square > k
	
	int pivot = (sqr+1)*(sqr+1); //  first diagonal element > kthlargest
	int distance = pivot -k;  // to index into the merge array
	
	
	//using merge of mergesort to sort the elements below this diagonal element(in same column) and to the right of it in same row
	//and then finding the required answer
		
	int temp[] = new int[sqr];
	int temp2[] = new int[sqr];
	
	for(int i=1;i < sqr+1;i++)
	{
	
		temp[i-1] = a[n-(sqr+1)][n-(sqr+1)+i];
		temp2[i-1] = a[n-(sqr+1)+i][n-(sqr+1)];
		
	}
	
	int temp3 = 2 * (sqr);
	
	int res[] = new int[temp3];
	
	res = merge(temp,temp2);
	
	//System.out.println("merged array is" + Arrays.toString(res));
	
	return res[distance-1];
	
	
}

- Anonymous February 02, 2013 | Flag Reply

public class KthMax {
	
	static void kthmax(int[][] matrix, int k) {
		int row = matrix.length;
		int column =  matrix[0].length;
		System.out.println("row = " + row + " column = " + column);
		
		// sort matrix
		int[] array = new int[row * column];
		
		for (int i=0; i < column; i++) array[i] = matrix[0][i]; 
		
		for (int i = 1; i< row; i++) {
			merge(array, (i+1)*column, matrix[i]);
		}
		
		for (int x: array) System.out.print(x + ", ");
			
		//get k-th max
		int index = array.length - 1;
		while (k>0) {
			if (k == 1) {
				System.out.println("\nk-th max = " + array[index] + " index = " + index);
				break;
			}
			else {
				while (array[index-1] == array[index]) index--;
				index--;
				k--;
			}
		}
	}
	
	private static void merge(int[] array, int size, int[] y) {
		int indx = size - y.length -1;
		int indy = y.length-1;
		array[--size] = y[indy--];

		while (indy >=0) {
			if (y[indy] >= array[indx]) array[--size] = y[indy--];
			else array[--size] = array[indx--];
		}
	}
	
	
	public static void main(String[] args) {
		int[][] matrix = {{0, 1, 2, 3,4},
				{5, 6, 8, 9, 11},
				{8, 10, 12, 13, 15},
				{9, 13, 15, 16, 16}};
		kthmax(matrix, 3);
	}

}

- Happy February 03, 2013 | Flag Reply

A key observation is that elements on the matrix boundaries(bottom row and rightmost column) are larger than those bounded by them. The kth max element can be found by peeling the matrix layer by layer. This is done by two steps. 1) find the layer which the kth maximum value lies on. 2) identify the target value on such found layer. The first step is trivial: continuously subtracting current layer size(number of elements) from k until k reaches zero or negative. Once the proper layer is identified. The problem reduces to find the k-th maximum value(remember here, k has changed) on that layer. As the elements on the layer are sorted. The largest one is on the bottom right, moving left or up getting smaller values. This scenario is similar to the step of merging two sorted subarrays in the merge-sort problem. A c++ implementation is as below,

double kthmax_sorted_matrix(double* matPtr, int w, int h, int k)
{
///the matrix is sorted. peel the matrix from outside to insides
///determine which layer the kth maximum values lies on
unsigned int layerSize = w + h -1;
unsigned int layerIndex = 0;
while((k - layerSize) > 0)
{
layerSize -= 2;
k -= layerSize;
layerIndex++;
}
unsigned int layerWidth = w - layerIndex;
unsigned int layerHeight = h - layerIndex;
///now find the k-th maximum value at this layer
unsigned int startRowI = layerHeight - 1;
unsigned int startRowJ = layerWidth - 1;
unsigned int startColI = layerHeight - 1;
unsigned int startColJ = layerWidth - 1;
double kMax = -1;
while( k-- > 0)
{
///get the row and col value and compare
double rowVal = matPtr[ startRowI * layerWidth + startRowJ];
double colVal = matPtr[ startColI * layerWidth + startColJ];
if(rowVal > colVal)
{
///move to left
startRowJ--;
kMax = rowVal;
}
else
{
startColI--;
kMax = colVal;
}
}
return kMax;
}

- mana February 03, 2013 | Flag Reply

You may check question?id=15316686

- Shashi February 04, 2013 | Flag Reply

for example:
array is : 1 4 8 12
5 9 13 21
7 15 19 23
the elements go in decresing order diagonally
first 23, 21,19, 12, 13, 15,9,8,7,5,4,1...........
basically take diagonal by diagonal and sort them and put them in array and find kth largest element

- meghana February 04, 2013 | Flag Reply

Taking all elements and sort it won't be a good way..
I am considering constructing a 'candidate pool' and adding and erasing elements to the pool in each step;
For example, for this array
1 4 8 12
5 9 18 21
7 15 19 23
The 1st smallest would be a[2][3], then construct a pool of [1,3] [2,2] for next step
The 2nd smallest is a[1][3](21) (we just choose from the pool construct from previous step);
Then erase [1,3] from pool, adding [0,3][1,2] to the pool, now the pool have [0,3] [1,2][2,2]
(You can notice that in this pool,[1,2], couldn't be a candidate since [2,2] is in the pool, probably we can filter it by using comparison before adding to pool.
Then repeat the previous steps until finding kth largest....
Probably works......

- Beserk February 04, 2013 | Flag Reply

anyone has an idea to do it in-place?

- vincent February 04, 2013 | Flag Reply

It can be done in place, and quite efficiently. What you need to do is build a "map" array of the same dimensions and then populate it with indicators of the largest number, next largest, etc. For example:

1 7 8 14
5 11 10 18
7 12 15 19
20 25 16 21

Initialize the "map" array to zeros:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

You know the largest value will be in the bottom row, since every row is sorted. So you scan the lowest non-map-occupied spaces in each row (in this first pass the bottom row) and note the location of the largest value. You fill in the corrsponding space in the map array with a 1 (largest value is 1, second largest 2, etc.)

0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0

You again scan the lowest non-map-occupied spaces in each row for the second lowest value. You scan 20,12,16, and 21; and put a 2 in the map array entry corresponding to 21:

0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 2

repeat scanning the lowest non-map-occupied spaces in each row until you hit the the nth count. If n is 5 you get this map:

0 0 0 0
0 0 0 5
0 0 0 4
3 1 0 2

Thus the second row, 4th column is the 5th highest value. This works for all values of n, but is especially efficient for the larger values in the table. I think it's about as efficient as the merge sort someone mentioned except that you don't (usually) have to sort the whole table.

- stitch626 February 05, 2013 | Flag Reply

This is my solution in Java. It only solves for unique numbers and it doesn't take into account any repeated element

public class Test1{

	public static void main (String[] args){
		int[][] data = new int[][]	{{2,5,7,9,14,16}, 
									 {3,6,8,10,15,21},
									 {4,7,9,15,22,35}, 
									 {7,8,9,22,40,58}};
									 
		System.out.println(findKthLargestElement(data,7));
	}
	
	public static int findKthLargestElement(int[][] data, int k){
		int width = data.length;
		int length = data[1].length;
		int numElements = width*length;
		int largest = data[width-1][length-1];
		int found = 1;
		
		while(found < k){
			int j = 0;
			for(int i=0; i < numElements; i++){
				if(data[i/length][i%length] >= largest) continue;
				if(data[i/length][i%length] > data[j/length][j%length])j=i;			
			}
			largest=data[j/length][j%length];
			found++;
		}
		return largest;
	}
	
}

- Geraz February 07, 2013 | Flag Reply

int k = 3;
		
		int[][] elem = getArray();
		int colLength = elem[0].length;
		int rowLength = elem.length;
		int total = rowLength * colLength;
		
		System.out.println(rowLength+", "+colLength);
		
		TreeSet<Integer> tt = new TreeSet<Integer>();
		
		for (int i =0; (i < rowLength); i++) {
			for (int j =0; j < colLength; j++) {
				tt.add(elem[i][j]);
			}
		}

		Set<Integer> desc = tt.descendingSet();
		Integer[] desI = new Integer[total];
		desc.toArray(desI);
		
		System.out.println("kth:"+k+"==>"+desc);
         	System.out.println("kth:"+k+"==>"+desI[k-1]);

- Anonymous February 08, 2013 | Flag Reply

Convert the 2d array into a 1d array(or treat it like a 1-d array), and then solve the standard selection problem using the quicksort partition function.Time complexity:O(no_of_elements),O(n^2)

- s03bans February 13, 2013 | Flag Reply

k-th largest element will be definitely located in subset [0..k-1],[0..k-1], as far the rows and columns are sorted, the k-th element is greater than any [0..k-2] element for each row/column.

int max_item = m[k][k];
for(int i = k-1; i >=0; i--)
{
int max1 = max(m[0][i],m[i][0]);
if(max1 >max_item)
max_item = max1;
else break;
}

worst case complexity O(k)

- dubovoy.vladimir February 18, 2013 | Flag Reply

constant* nlog(m) solution
try it!

int binSearchLessNum(int* M,int n,int value){
	int left=0,right=n-1;
	while(left<right-1){
		int mid=left+(right-left)/2;
		if(M[mid]<=value)
			left=mid;
		else right=mid;
	}
	
	if(M[right]<=value)		
		return right+1;
	else if(M[left]<=value)
		return left+1;
	else {return left;}
}
int findKth(int(*M)[4],int m,int n,int k,bool& err){
	err=false;
	if(k<1||k>m*n){
		err=true;
		return 0;
	}
	int valueL=M[0][0];
	int valueR=M[m-1][n-1];
	while(valueL<valueR){
		int midValue=valueL+(valueR-valueL)/2;
		int numLess=0;
		bool hasValue=false;
		for(int i=0;i<m;++i){
			bool flag;
			int num=binSearchLessNum(M[i],n,midValue);
			if(num>0&&M[i][num-1]==midValue)hasValue=true;
			numLess+=num;
		}		
		if(numLess==k&&hasValue==true)return midValue;
		if(numLess>=k)valueR=midValue-1;
		else valueL=midValue+1;
	}
	return valueL;
}
int main(){
	int M[4][4]={
		1,1,1,2,5,6,7,8,9,10,11,12,13,14,15,16
	};
	bool err;
	for(int i=0;i<16;++i){
		printf("%d ",findKth(M,4,4,i+1,err));
	}
	return 0;
}

- sunnyandcloudy2 February 19, 2013 | Flag Reply

Python

Assumption:
if the 5 largest elements are all “100” and the 6th largest is “99”, then the 6th largest is “99”. 99 is not the “2nd largest”, 100 is.

class Matrix:
    def __init__(self,rowlist):
    	self.rowlist = rowlist

def find_kth_largest_element2(matrix1, k):
    queue1=[]
    for row in matrix1.rowlist:
        for cell in row:
            if len(queue1) == 0:
                queue1.append(cell)
            elif len(queue1) > 0 and cell > queue1[0]:
                queue1.append(cell)
                queue1=sorted(queue1)
                if len(queue1) > k:
                    queue1.pop(0)
    return queue1[0]

x1 = Matrix([[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]])

print find_kth_largest_element2(x1, 5)

>>> 
11

- mikeolteanu June 16, 2013 | Flag Reply

typedef pair<int, int> pii;
typedef pair<int, pii> piii;

int findKlargest(int a[][], int n, int k)
{
             assert(k <= n);
             priority_queue< piii> Q;
             Q.push( piii(a[m-1][n-1], pii(m-1,n-1) )
             while (--k && !Q.empty())
             {
                   piii p = Q.top(); Q.pop();
                   int i = p.second.first, j = p.second.second;
                   if (i-1 >= 0) Q.push( piii(a[i-1][j], pii(i-1,j)) );
                   if (j-i >=0 ) Q.push ( piii(a[i][j-1], pii(i,j-1)) );
             }
             return Q.top().first;
}

- fafdu July 06, 2013 | Flag Reply

When you think about it. If you start at the bottom left or the bottom right of the array you have a structure that is similar to a binary tree. Basically the element to the left of the current element is greater and the element bellow the current element is greater! So really you can solve this in O(m) worst case.

bool findVal (int[][] array, int m, int expectedVal)
{
int x=m- 1;
int y= 0;

while( x >= 0&& y <m)
{
	if (array[x][y] == expectedValue)
		return true;
	else if (array[x][y]  < expectedValue)
		x--;
	else
		y++;
		
}
return false;

- tipbruley September 05, 2013 | Flag Reply

posted wrong solution

- S.Abakumoff January 27, 2013 | Flag Reply

int kthLargest(int matrix[][], int k ){
  int m = matrix.length; // Number of rows
  int n = matrix[0].length; // Number of Cols
  if( k > m*n) {
     return -1;
  } // Not found
  else {
    int rowNumber = (int)Math.ceiling(k/n) - 1;
    int colNumber = k - n * rowNumber -1;
    return matrix[rowNumber][colNumber];
  }
}

Example
1 2 3 4
9 10 11 12

K = 5
rowNumber = Ceiling(5 / 4) -1 = 2 - 1 = 1
colNumber = 5 - 1 * 4 - 1 = 0

Answer :
matrix[1][0] = 9

- Rajat January 27, 2013 | Flag Reply

Here is what I thought

Last element will be the largest
The diagonal just above the last element will have elements smaller to largest and greater than others

Eg.
I am taking a 3x3 matrix

4 9 11
5 13 15
6 16 25

Now 25 will be largest
Next diagonal elements are 16 and 15
Other next are 6 13 11

Hence we can calculate the kth max element by finding the diagonal where the kth number can be and then finding the kth element from that diagonal

- DashDash January 27, 2013 | Flag Reply

Simply get a (one dimension) pointer to the matrix, and return the k-th element:

#include <stdio.h>

int main(void) {
        int k=2;
        int matrix[3][3] = {1,2,3,4,5,6,7,8,9};
        int *arr = (int *)matrix;
        int size = sizeof(matrix)/sizeof(**matrix);

        printf("the largest k=%d-th in matrix of %d elements is %d\n",
                k, size, arr[size-k]);
        return 0;
}

- Ali February 01, 2013 | Flag Reply

for a sorted matrix, isnt the last element i.e. mat[m][n] is the largest element ?

- DashDash January 27, 2013 | Flag Reply