Concise java solution with comments 36ms


  • 0
    G
    public class Solution {
        class Element{
            int x, y, val;
            public Element(int x, int y, int val) {
                this.x = x;
                this.y = y;
                this.val = val;
            }
        }
    
        public int kthSmallest(int[][] matrix, int k) {
            int x = 0, y = 0;
            int m = matrix.length, n = matrix[0].length;
            PriorityQueue<Element> pq = new PriorityQueue<Element>(11, new Comparator<Element>(){
                public int compare(Element e1, Element e2) {
                    return e1.val - e2.val;
                }
            });
            pq.offer(new Element(x, y, matrix[x][y]));
            for (int i = 1; i <= k - 1; i++) {
                Element e = pq.poll();
                //Go down to add element
                if (e.x + 1 < m) {
                    pq.offer(new Element(e.x + 1, e.y, matrix[e.x + 1][e.y]));
                }
                //only add element from right when current element is at the first row, then we are able to cover 
                //all columns without any duplicates
                if (e.y + 1 < n && e.x == 0) {
                    pq.offer(new Element(e.x, e.y + 1, matrix[e.x][e.y + 1]));
                }
            }
            return pq.poll().val;
        }
    }
    

Log in to reply
 

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