MinHeap Java solution - matrix is a lattice


  • 0
    D
    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);
            visited.add(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);
                    visited.add(downCell);
                }
                Cell rightCell = new Cell(smallest.x, smallest.y + 1);
                if (rightCell.isValid() && !visited.contains(rightCell)) {
                    minheap.offer(rightCell);
                    visited.add(rightCell);
                }
            }
            return 0;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.