HEAP_LC378

class Solution {

    class Node {
        int value;
        int row;
        int col;

        Node(int value, int row, int col) {
            this.value = value;
            this.row = row;
            this.col = col;
        }
    }
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<Node> minHeap = new PriorityQueue<>(
            (a, b) -> a.value - b.value
        );
        for (int i = 0; i < n; i++) {
            minHeap.offer(new Node(matrix[i][0], i, 0));
        }
        int ans = 0;
        while (k > 0) {
            Node curr = minHeap.poll();
            ans = curr.value;
            k--;
            if (curr.col + 1 < n) {

                minHeap.offer(
                    new Node(
                        matrix[curr.row][curr.col + 1],
                        curr.row,
                        curr.col + 1
                    )
                );
            }
        }

        return ans;
    }
}