# MinHeap Java solution - matrix is a lattice

• ``````public class Solution {
private int m;
private int n;
private int[][] matrix;

class Cell implements Comparable<Cell> {
int x;
int y;
public Cell(int x, int y) {
this.x = x;
this.y = y;
}
public boolean isValid() {
return x >= 0 && x < m && y >= 0 && y < n;
}
@Override
public int compareTo(Cell otherCell) {
return matrix[x][y] - matrix[otherCell.x][otherCell.y];
}
@Override
public boolean equals(Object other) {
if (!(other instanceof Cell)) {
return false;
}
Cell otherCell = (Cell)other;
return x == otherCell.x && y == otherCell.y;
}
@Override
public int hashCode() {
int hash = 17;
hash = hash * 31 + x;
hash = hash * 31 + y;
return hash;
}
}

public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return 0;
}
this.m = matrix.length;
this.n = matrix[0].length;
this.matrix = matrix;
Set<Cell> visited = new HashSet<>();
Queue<Cell> minheap = new PriorityQueue<>();
Cell firstCell = new Cell(0, 0);
minheap.offer(firstCell);
int seen = 0;
while (!minheap.isEmpty()) {
Cell smallest = minheap.poll();
seen++;
if (seen == k) {
return matrix[smallest.x][smallest.y];
}
Cell downCell = new Cell(smallest.x + 1, smallest.y);
if (downCell.isValid() && !visited.contains(downCell)) {
minheap.offer(downCell);
}
Cell rightCell = new Cell(smallest.x, smallest.y + 1);
if (rightCell.isValid() && !visited.contains(rightCell)) {
minheap.offer(rightCell);