Find K-th Element in a Sorted 2-Dimensional Array

[Question]
Suppose there is a 2 dimensional array MxN, data in each column and row is in ascending order. Find k-th smallest element in this array.

[Analysis]
Merge sort can resolve this problem. but it may not make sense to build a min-heap of size M, when M>>K.

The first three elements in left-top corner of the array (A(0,0), A(0,1), A(1,0) ) make a natural heap. So first, we build a size 3 min heap, using A[0,0], A[0,1], A[1,0]; then
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j], 
pick up [i+1,j] and [i,j+1]). 
3)Loop through 1),2) K-1 times; We got K-th elements at the root of the heap.

The time complexity is O ( K Log K ). For each loop, heap size increase at most one, so the heap size is at last K. And the code needs to run K loops. 

Further analysis: the algorithm above works well when K<<M and K<<N. When K is close to M or N, or K> M or N, the heap's maximum size in algorithm is M+N. So the time complexity will become O ( K Log (M+N) ). The good solution for this problem is to select the heap first: use either columns (N), rows(M) or diagonals (K). Selection depends the minimum of three sizes. The complexity will be: O( K Log Min(M, N, K) ).

[Similar Questions]

(1) This looks similar but is actually different, to find a value in a sorted 2-Dimensional Array. That can be resolved in time O(N).

(2) Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.  

// Binary search can apply on this question.

[Solution]


package com.mysrc.algortest;
import java.util.*;

public class MatrixSort implements TestCaseRunner {
class MatrixNode implements Comparable{
int x;
int y;
int value;

MatrixNode( int x, int y, int val) {
this.x = x;
this.y = y;
value = val;
}

public int compareTo(Object other) {
if (!(other instanceof MatrixNode)) {
throw new ClassCastException("Invalid object");
}

MatrixNode a = (MatrixNode) other;

if (this.value < a.value) return -1;
if (this.value > a.value) return 1;
return 0;
}
}

public int findKthElementInSortedMatrix(int[][] m, int k) {
PriorityQueue<MatrixNode> heap = new PriorityQueue<MatrixNode>();

heap.add(new MatrixNode(0,0, m[0][0]));
heap.add(new MatrixNode(0,1, m[0][1]));
heap.add(new MatrixNode(1,0, m[1][0]));

m[0][0] = -1;
m[0][1] = -1;
m[1][0] = -1;

MatrixNode head = null;

while (k-->0) {
head = heap.remove();
System.out.println("X,Y, V == " + head.x + "," + head.y + "," + head.value);

if (head.x < m.length-1 && m[head.x+1][head.y] != -1) {
heap.add(new MatrixNode(head.x+1, head.y, m[head.x+1][head.y]));
m[head.x+1][head.y] = -1;
}

if (head.y < m[0].length-1 && m[head.x][head.y+1] != -1) {
heap.add(new MatrixNode(head.x, head.y+1, m[head.x][head.y+1]));
m[head.x][head.y+1] = -1;
}
}
return head.value;
}

public boolean runTestCases() {
MatrixSort msort = new MatrixSort();

int[][] arr = {
{1,   3,  5,  7,  9,  11, 13, 15, 17},
{2,   6,  8, 12, 13,  14, 15, 16, 17},
{8,  10, 12, 14, 16,  18, 18, 18, 18},
{9,  10, 13, 15, 17,  19, 21, 23, 25},
{11, 12, 13, 19, 20,  21, 24, 28, 30},
{15, 16, 17, 19, 20,  22, 29, 30, 31},
{18, 19, 20, 21, 22,  23, 30, 31, 33}
};

msort.findKthElementInSortedMatrix(arr, 13);

return true;
}
}