[Algo] 26. Kth Smallest Number In Sorted Matrix

public class Solution {
  public int kthSmallest(int[][] matrix, int k) {
    // Write your solution here
    int row = matrix.length;
    int col = matrix[0].length;
    boolean[][] isVisited = new boolean[row][col];
    PriorityQueue<Cell> pq = new PriorityQueue<>(k, new Comparator<Cell>() {
      @Override
      public int compare(Cell a, Cell b) {
        return a.value - b.value;
      }
    });
    pq.offer(new Cell(0, 0, matrix[0][0]));
    isVisited[0][0] = true;
    for (int i = 0; i < k - 1; i++) {
      Cell cur = pq.poll();
      int curRow = cur.row;
      int curCol = cur.col;
      if (curRow + 1 < row && !isVisited[curRow + 1][curCol]) {
        pq.offer(new Cell(curRow + 1, curCol, matrix[curRow + 1][curCol]));
        isVisited[curRow + 1][curCol] = true;
      }
      if (curCol + 1 < col && !isVisited[curRow][curCol + 1]) {
        pq.offer(new Cell(curRow, curCol + 1, matrix[curRow][curCol + 1]));
        isVisited[curRow][curCol + 1] = true;
      }
    }
    return pq.poll().value;
  }
}

class Cell {
  int row;
  int col;
  int value;
  public Cell(int row, int col, int value) {
    this.row = row;
    this.col = col;
    this.value = value;
  }
}