package maxtrix;

import java.util.PriorityQueue;

public class MatrixNthSmallest {

	public int getNthSmallestValue(int[][] metrix, int n) {
		if (metrix == null 
				|| metrix.length == 0
		      || metrix.length * metrix[0].length < n 
		      || n <= 0) {
			throw new IllegalArgumentException("invalid metrix");
		}
		boolean[][] metrixVisited = new boolean[metrix.length][metrix[0].length];
		PriorityQueue<Cell> pq = new PriorityQueue<>();
		pq.add(new Cell(metrix[0][0], 0, 0));
		metrixVisited[0][0] = true;
		for (int i = 0; i < n - 1; i++) {
			Cell cell = pq.poll();
			if (cell.i + 1 < metrix.length && !metrixVisited[cell.i + 1][cell.j]) {
				pq.offer(new Cell(metrix[cell.i + 1][cell.j], cell.i + 1, cell.j));
				metrixVisited[cell.i + 1][cell.j] = true;
			}
			if (cell.j + 1 < metrix[0].length
			      && !metrixVisited[cell.i][cell.j + 1]) {
				pq.offer(new Cell(metrix[cell.i][cell.j + 1], cell.i, cell.j + 1));
				metrixVisited[cell.i][cell.j + 1] = true;
			}
		}
		return pq.poll().value;
	}

	public static class Cell implements Comparable<Cell> {
		public int value;
		public int i;
		public int j;

		public Cell(int value, int i, int j) {
			this.value = value;
			this.i = i;
			this.j = j;
		}

		@Override
		public int compareTo(Cell t) {
			return value - t.value;
		}
	}
}