## Google Interview Question

Software Engineer / DevelopersIf the each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom, isn't the k-th largest number will lie in the bottom right k*k matrix? Also I think we need a min-heap rather than max-heap since we want to find k-th largest. Min-heap will keep the largest k elements at the end, but Max-heap will keep the smallest k elements. Plz correct me if I am wrong. Thanks

Whether it's top left or bottom right does not really matter, you know what I mean ...

Both min-heap and max-heap is fine, it's just two different ways to find k largest numbers. What you suggest is correct approach and I think the method I wrote original is also right. The difference is that you store the results in the heap, while I put the results outside the heap

I am not sure I am following your logic here. Would you care to explain? If you are putting a max heap to find the largest element from the first element of each row in the k x k matrix, shouldn't that just be the kth row's first element? Doesn't the heap described by solution just to find the [k][k] element of the k x k matrix? That shouldn't be the correct answer. Example { [ 0, 1] [ 2,4 ] } max heap give you 2 on the first loop, then goes down the row to find 4, which is the 4th largest element instead the second largest I want to find.

Only the elements above or on the main diagonal in the k*k matrix need to be considered.

Close.

You need to look at the

`sqrt(k)th`

value along the diagonal.

Consider this recursive relationship:

The nth square along the diagonal is greater than every where above it, because we sorted the columns. It is also greater than every row to the left of it, because we sorted the columns.

By induction, the nth square along the diagonal is greater than all n^2 squares to its upper left (by recursing the relationship described above)

So every nth square along the diagonal is greater than n^2 elements.

Call the kth largest value n^2, where n is the nth square along the diagonal. To find this square, so we have

`k = n^2, and n = sqrt(k)`

For non perfect square k's, check adjacent squares appropriately.

aka, this can be done in constant time.

Let me make an adjustment ...

For non perfect square ks, just look at the two multiples of k that are closest in value to each other.

For example, consider the 12th largest element. It's not a perfect square, but it has two multiples close to each other {{4 and 3}}. So the 12th largest element after sorting will be at either {{Grid[(4 - 1)][(3 - 1)] or Grid[(3 - 1)][(4 - 1]}}

Edit

My comments are stupid. Disregard. The

`sqrt(k)`

th diagonal square is not necessarily the exact the kth largest ... it's just greater than k elements. Doh.

To find the kth largest shouldn't we consider the matrix of size ceil(sqrt(k))*ceil(sqrt(k)). For instance in a 6 x 6 matrix to find the 10th largest, we must consider the bottom right matrix of size 4 x 4 which will have the max 16 elements of the original matrix and we create a (max)heap of size 10.

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))

Yep, I got the same idea. Here is an incomplete implementation, but I think is enough.

```
void rebuild(int **a, int cur_i, int cur_j, int r, int c){
int i = cur_i, j = cur_j;
if((cur_i + 1 <= r || cur_j <= c) && cur_i+1 <= r+c){
if(a[cur_i+1][cur_j] < a[i][j]){
i = cur_i +1;
}
}
if((cur_i <= r || cur_j + 1 <= c) && cur_j+1 <= r+c){
if(a[cur_i][cur_j+1] < a[i][j]){
j = cur_j +1; i = cur_i;
}
}
if(i != cur_i || j != cur_j){
swap(a[cur_i][cur_j], a[i][j]);
rebuild(a, i, j, r, c);
}
}
void rebuild(int **a, int r, int c){
rebuild(a, 0, 0, r, c);
}
void FindKth(int **a, int len, int k){
int part = (len+1)*len/2;
if(k <= part){
int r = 0, c = len -1;
int i = 1;
while(i++ != k){
swap(a[0][0], a[r][c]);
if(--c < 0){
c = r - 1; r =0;
}else{
r++;
}
rebuild(a, r, c);
for(int i = 0; i < len; ++i){
for(int j = 0; j < len; ++j){
cout<<a[i][j]<<", ";
}
cout<<endl;
}
cout<<endl;
};
cout<<a[0][0];
}else{
cout<<"Ignored, if k is in the lower part, the process is similar, we can treat the lower part of the matrix as a max-heap");
}
}
```

ok so the correct complexity for this problem is O(k*(m+n)) right? there are so many people suggesting O(k log (n)) i just don't see how. and they don't do a good job explaining either.

Search for "young tableau" and look for a link with title "CSE 3358 Problem Set 5..." The solution to problem 1c describes this idea in more details and also gives pseudo-code

Having said that, the user who asked this question mentioned that the interviewer said you can't modify the matrix nor use heap etc, so maybe the interviewer has another algorithm in mind

you can use modified binary search here.

you know elements are sorted. so for matrix n*m

lets divide it into 4 parts.

| 1. k < n*m/4 | 2. k< n*m/2 |

| 3. k< n/2*m | 4. k< n*m |

now

if k < n*m/4 . then kth element can't be in any other part than 1.

if k< n*m/2 then kth element will be in 2 or 3.

if k< n*m then kth element will be in 4

now you found where to repeat search. do it recursively. you will get so many kth element (e.g you will get 2 kth element from searching 2 and 3 matrix).

for each kth element found print the smallest one. that is the actual kth element.

complexity. x* log(x) where x = max(n,m)

Consider the matrix (with n = 4 & m = 4):

1444

2444

3444

4444

If k=3, and that we are looking for the kth smallest element, I think the answer is 3, but it's not in your upper-left submatrix though...

```
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)
```

Why are you creating another heap when the input matrix is itself a heap? I would't recommend using high level library routines for programming interviews, since they trivialize the original problem. Do you think you should use the built-in sort() routine when the interviewer is asking you to write mergesort code?

It's a nice idea to think about the sorted matrix as a heap, and indeed one simply perform remove-top operation to get the next smallest value. However since the matrix contains N^2 items and its equivalent to a heap of height N, so the remove operation will be O(N). So to find the first K smallest items will take O(K log N).

In my solution it will take O(K log K), because the heap I'm creating will have no more than K items in it. It starts with just one element, and as elements are removed we add other elements in their place - a maximum of 2 elements added for each one removed, so the maximum size of the heap is K.

Using a heap is perfectly valid here, just like it is in heap-sort, or Dijkastra shortest path algorithm. If needed, it's trivial to actually implement the actual heap remove and insert methods.

Correction: chisingh's idea of using the matrix as a heap of height N, will actually take O(KN) time. Compare that to my solution which is O(K log K), as I'm building a new heap that will only contain the items that need to be considered next (the items adjacent to the previous items removed from the matrix). The new heap will have a maximum of K items in it, and in most cases it will be even smaller.

@chisingh. LOL! Using library provided data-structures like heaps in encouraged, and is looked at as a good sign! No sane interviewer will expect you to implement a standard data-structure if that is just something you are using as part of a bigger solution. You can assume it is there.

The reason not to use that here is the in-place requirement.

The trivialize part is when the question is about implementing that data-structure/method. Like if they say write code to copy strings, saying you will use strcpy will get you a no hire.

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)))

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.

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

my python code:

```
def kthLargest(k,N,inputs):
def myCMP(x,y):
return cmp(x[2],y[2])
frontiers = [(0,0,inputs[0][0])] #cell of frontiers, tuple by row, col and its val
cnt = 0
while cnt < k and frontiers:
cur = frontiers[0]
cnt += 1
right, down = cur[0] + 1, cur[1] + 1 #moving right and down
frontiers = frontiers[1:] #dequeue the first
if down < N:
x = (cur[0],down,inputs[cur[0]][down])
if x not in frontiers: #skipping the one has been visited
frontiers.append(x)
if right < N:
x = (right,cur[1],inputs[right][cur[1]])
if x not in frontiers:
frontiers.append(x)
frontiers.sort(cmp=myCMP)
return cur[2]
```

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.

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).

```
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];
}
```

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

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);
}
}
```

Hello manish,

How can we call these k times I mean how??

It will not show any change in the matrix!!

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]))
```

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

```
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]);
}
```

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

```
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;
}
```

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);
}
}
```

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)

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

}}

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.)

start from largest element - a[n][n]

traverse back K elements, each "traverse" requires at most 5 comparisons-O(1)

O(k)

```
#!/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)
```

Given that the rows and columns in the matrix M are all sorted in an ascending order, the k th largest element can be found in constant time ,that is O(1)time complexity.

row =n- k/n -1

column = n - k%n -1

the element is M[row][column]

But does it work?

is the formula like this?

row = (n-k)/(n-1)

column = (n-k)%(n-1)

Whatever form it is, I don't think it works.

```
1 10 20 30 40
2 11 21 31 41
3 12 22 32 42
4 13 23 33 43
5 14 24 34 44
```

In this matrix, 5th smallest is 5.

```
1 10 20 30 40
2 11 21 31 41
3 12 22 32 42
4 13 23 33 43
12 14 24 34 44
```

In this it is 10.

Are you being funny by posting this formula? Can u explain it with example if not?

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.

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.

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).

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

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

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.

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).

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.

```
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];
}
```

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

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.

/*

Here is the complete code.

Assume that there is no duplicated element in the matrix.

If handling duplicated element, I will use a HashSet to record seen element.

*/

public class RowColumnSortedMatrix {

int[][] matrix;

public RowColumnSortedMatrix(int[][] matrix){

this.matrix = matrix;

}

public int[] findKthLargest(int k){

int[] result = new int[2];

if(k>matrix.length*matrix.length){//validate input

result[0] = -1; result[1] = -1;

return result;

}

int rowX=matrix.length-1, rowY = matrix.length-1;

int colX=matrix.length-1, colY = matrix.length-1;

int maxX=-1, maxY=-1;

int curRow = matrix.length-1, curCol = matrix.length-1;

int count=0;

while(count<k){

if(matrix[rowX][rowY]==matrix[colX][colY]){//pointed element equal, move both rowPointer and colPointer

count++;

maxX = rowX; maxY = rowY;

rowX = rowX-1;

if(rowX<0){ rowX = curRow-1; rowY = rowY-1; curRow--;}

colY = colY-1;

if(colY<0){colY = curCol-1; colX = colX-1; curCol--;}

}

else if(matrix[rowX][rowY]<matrix[colX][colY]){//element pointed by colPointer is bigger, move colPointer

count++;

maxX = colX; maxY = colY;

colY = colY-1;

if(colY<0){colY = curCol-1; colX = colX-1; curCol--;}

}

else{//element pointed by rowPointer is bigger, move rowPointer

count++;

maxX = rowX; maxY = rowY;

rowX = rowX-1;

if(rowX<0){ rowX = curRow-1; rowY = rowY-1; curRow--;}

}

}

result[0] = maxX; result[1]=maxY;

return result;

}

public static void main(String[] args){

int[][] matrix = {

{0,1,2,3},

{12,14,17,36},

{13,15,18,40},

{50,60,70,80}

};

RowColumnSortedMatrix sortedMatrix = new RowColumnSortedMatrix(matrix);

int[] xy = sortedMatrix.findKthLargest(11);

System.out.println("x= "+xy[0]+"; y= "+xy[1]+" element= "+matrix[xy[0]][xy[1]]);

}

}

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 :).

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.

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;
}
```

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

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]);

}

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)).

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.

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.

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)

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.

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);
}
```

Store this array in a file "2darray_k.in" in the following way.

4 5

1 2 7 10 21

3 4 8 11 22

5 6 9 12 23

13 14 15 27 28

Run my code below. You will get a ascending sequence. If you want to k-th element, just stop at the i-th item in the sequence.

```
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=10;
const int MAXINT=1000;
int array[MAXN][MAXN];
int M,N;
void init()
{
ifstream fin("2darray_k.in");
fin>>M>>N;
for (int i=0;i<M;i++)
for (int j=0;j<N;j++)
fin>>array[i][j];
fin.close();
}
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]<<" ";
InOrder(x+1, y, array[x][y], high);
}
}
int main()
{
init();
InOrder(0, N-1, -MAXINT, MAXINT);
cout<<endl;
}
```

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).

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;
}
```

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
}
}
```

```
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);
}
}
}
}
```

```
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;
}
```

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.

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.

Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order.

rows = no. of rows

cols = no. of cols

```
if(k > rows * cols) return error_code;
if(k == rows * cols) return m[0][0];
r = rows - 1 - (k / cols);
c = cols - ( k % cols);
return m[r][c];
```

Are you sure this works? I tried it but it didnt work.

```
int [][]m = {{1, 2, 3, 25}, {4, 23, 20, 88}, {7, 82, 90, 100}, {8, 83, 91, 101}};
// kthLargest def -> (matrix, k, row, column)
System.out.println(kthLargest(m, 2, 4, 4));
```

It should print 100, but prints 91

Let us assume it to be a square matrix.

And the total elements are N.

We have to find the Kth element from the last.

As right most bottom would be the first element from the last.

Second last diagonal element would be 4 th element from the last. This trend goes on something like

square(1), square(2), square(3)......

We have to find out the smallest perfect square equal to or bigger than k.

Suppose k=8 then perfect square would be 9.

Now the 9th element from the last we have found.

In order to get the 8th largest element we have to find it out

in the matrix from A[n-3][n-3] to A[n-3][n] and A[n-3][n-3] to A[n][n-3].

We will sort these elements and will find out the 9-8 = 1 element in the sorted ones. This would be our desired element.

1 2 3 25

4 23 20 88

7 82 90 100

8 83 91 101

Sort the matrix =>

1 2 3 4

7 8 20 23

25 82 83 88

90 91 100 101

k = 2;

rows = 4

cols = 4

r = 4 -1- (2/4) = 3 - 0 = 3;

c = 4 - (2%4) = 4 - 2 = 2;

the result is element m[3][2] = 100

P.s. When I asked how is the matrix sorted and u said left-> right & top to bottom.. that means that your matrix is already sorted as I reorganized it. If not than it will take time to do it .

Better solution is this : http://www.quora.com/How-can-you-efficiently-determine-the-k-th-maximum-element-in-a-MxN-sorted-matrix

two solution, one is recuison 1) matrix block, the matrix can be divided into 4 block 2) from the left-down position, an example :

1 2 3 4

5 6 7 8

9 10 11 12 where k is 7.

9 > 7, so delete the last line, and go up, 5 < 7, the delete the first line, will find 6 .....matrix will be smaller and smaller, and finally get the destinetion

correct solution in 11 lines:

```
import heapq
def first_k_sorted_mat(mat, k):
h=[(mat[0][0], 0, 0)]
l=[]
for c in range(0, k):
(val, row, col)=heapq.heappop(h)
l.append(val)
if col==0 and row+1<len(mat):
heapq.heappush(h, (mat[row+1][col], row+1, col))
if col+1<len(mat[0]):
heapq.heappush(h, (mat[row][col+1], row, col+1))
return l
def main():
mat=[[1, 6, 10, 10],[2, 8, 12, 25], [9, 11, 20, 26]]
print mat
print first_k_sorted_mat(mat, len(mat)*len(mat[0]))
```

When I pop the first element of a row (e.g. M[row,0] ) from the heap (which means it's the smallest element for the current iteration), I'm adding the element below it (M[row+1, 0]) to the heap, because it might be the next smallest element.

This is done in addition to pushing into the heap the element to the right of the current smallest element (A[row, col+1]).

void main(){

int k,resultx, resulty;

int m = 10 , n = 13;

k=99;

if( k > m*n) { printf("out of bound");}

else {

resultx = k/n;

resulty = k%n ;

}

printf("%d %d",resultx,resulty);

}

```
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 }
```

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.

Sure. The main function is popping the largest element k times, and replacing it with the smallest one. After swapping these two elements we need to restore the original property of the matrix. That is precisely what pushUp() function does. Just like we have heapify() for max-heaps. Only difference is for an element at [i,j] we have [i-1][j] and [i][j-1] as its 'children'.

So you're treating the matrix as a heap ?? Interesting idea.

However, I'm not sure it's actually correct, because each item actually has two parents, and you compare it to both its parent. If the current item is smaller than one of its parents, and you swap them, then you have to again check that the swapped parent, which is now a child, is smaller than the other parent.

I don't think your code does that, because this will require each swap to incur two separate operations, so this would need a recursive solution.

Nive try, but it's incorrect and ineffiecient (because even if it was correct it would take O(KN)).

Really? You are not sure that it's actually correct. But I am.

Can you give me an input for which my program gives you an incorrect output?

The pushUp() is of the order of log(N), not O(N) as reported by you. Just refer to any other heap implementation to verify.

What's the point in misleading people and wasting your precious time and mine?

does the code produces correct output for input

[

[1, 2, 3, 25],

[4, 23, 20, 90],

[7, 82, 95, 96],

[8, 97, 99, 101]

]

and k = 6 which is 90 ?

So please explain how it works, and how you maintain the matrix as a heap or sorted matrix.

Alright, Let me try one more time.

As we know, each node in a max-heap can have at most children which are both smaller than the value of this node. Just like in array representation of heaps where children are located at 2*i+1 and 2*i+2, here in case of matrix, the children are located at [i-1][j] and [i][j-1]. There is absolutely no logical difference between this representation and the conventional array one. Now you just have to pop the root node of the heap k times and restore the original heap property by pushing up the node at [n][n] to it's correct place, where it is greater than its both children.

Please carefully look at the code to understand the rest of the minor details, since it's not easy to explain in words.

May be someone can provide a C/Java implementation of this method?

Yes, I understand the solution.

But if the matrix is NxN, then your pushUp method will perform 2N iterations, and you call this method K times, so overall time is O(KN) assuming the matrix is N*N.

My Solution is O(K log K) time regardless of the matrix size. Also your solution will only work for a square matrix (N by N) and my solution will work on any size matrix (M by N).

You see, by doing a push-Up operation into the matrix of size N-by-N, you incur a cost of O(N), which is unneccessary. In my solution because the heap I'm constructing only has K elements at most.

May be you are right. I personally do not like to use library routines for simple problems.

"No extra memory" can rule out your heapq completely.

I that case, feel free to do pushUp()s until you get the right answer. ;)

Look, your solution is simply inefficient, and as such it's not a good solution at all.

As for extra memory, you assume you can modify the matrix, but in most times you aren't allowed to modify the input, so in that case you would have to copy the matrix using additional O(N^2) space.

As for using heapq module, like I said, it's very simple to write the heap-insert and remove manually, I just used the available heap methods to save space here.

Last, there are many small issues with your code which won't be acceptable to interviewer, such as changing the used values to negative (won't work if the matrix has negative values, you need to use nulls - which will complicate your code).

Regarding coding style you shouldn't use semicolon at end of line (!?) in python, and properly indent after colon ":".

One more thing - if there was a rule not to use extra memory than I could modify my solution to use the matrix as the memory for the heap. I will simply use the cells along edges of the matrix opposite to the starting point, and treat them as an array for storing the heap.

In your solution, if the matrix cannot be modified then you will need to copy it which will take O(N^2) time and will waste O(N^2) space.

To chisingh: a few more clarifications regarding your solution.

First of all, you claim that the matrix is the same as an array representation of a heap. That's not correct. In the matrix each item has two parents, so it doesn't really represent a real tree like a heap (which is a binary tree).

For example, the matrix element M[1,1] is the child of both M[0,1] and M[1,0]. So each cell has two children, but it also has two parents (because it's shared by adjacent parents) !!

Another difference from a binary tree is that in each level of tree the number of nodes is double the previous level, but in the matrix the number of cells in the next diagonal is just one more than the previous diagonal. This affects the complexity of the algorithm, since operation on a heap takes log(M) time while operation of a matrix heap takes sqrt(M) (M = N*N, where N is the number of rows or columns in the matrix).

While this matrix-tree might behave like a binary tree here, I haven't heard of anyone suggesting it as a useful data structure for tree operations.....

@Chising: LOL! The burden of proof is on you. (Current) lack of a counter-example is not a proof of correctness.

Besides, when talking about an algorithm, correctness is not the only aspect that needs to be considered. The efficiency must be considered too (bogosort...).

Alright, I think this might work, heres my slight modification to this proof.

The bottom right element is always biggest. So we remove that at every instance, and replace it with an element smaller than the top left. Now to restore this property of the matrix, we must percolate up or left(the 2nd biggest element is either above it or to its left.) Either way it will take r+c swaps to move the element to the starting location(along the borders, so that the property is conserved).

This entire process needs to be repeated 'k' times to get the kth largest element.

The question asks for an in-place algorithm, and this is it.

Memory would be O(1), and Run time is O(K. (R+C)) Where R,C and dimensions(rows, col numbers), K is the kth largest to be fetched

This fetches all top k entries though, so it would not be as efficient as other methods to get top kth maybe

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...

You can. But there is no need to waste extra memory.

See my solution below for the right approach.

incorrect reply above.

navin.pd's solution of sorting all the matrix elements can be done in-place without requiring extra memory. we just treat the matrix as one (single-dimension) array and use some in-place sort.

The real problem is the inefiiciency of time - it would take O(N^2 log N) for a NxN matrix.

Additionally, chisingh's solution (to treat the matrix as a heap) is not a good solution as it requires O(KN) time which is also much worse than the optimal solution which O(K log K).

/*# 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);

}

```
#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);
}
```

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.

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);
}
```

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.

```
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];
}
```

```
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);
}
}
```

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;

}

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

What do you mean by decreasing order since there is 15 after 12,13 in the sequence you mentioned above...please clarify

cme from bottom first diagonal :23

next diagonal: 19 21

next diagonal: 15 13 12

next: 7, 9,8

next :5 4

next 1

so take each diagonal into temp array and sort them what i meant the elements in decreasing comes like first , first diagonal ements next second diagonal elemnts next third diagonal elemnts

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......

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.

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;
}
}
```

```
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]);
```

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)

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;
}
```

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
```

```
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;
}
```

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

```
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

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

what if the Matrix is:

1 2 5

2 3 6

3 4 7

the second diagonal is 4,6 but the third diagonal is 3 3 5, if I would like to search the 3th maximum number, your algorithm will print out 4 instead of 5.

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;
}
```

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

- Junxian.Huang February 19, 2013First 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!