378.Kth Smallest Element in a Sorted Matrix

1- PQUEUE

Solution 1 : Heap

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85173/

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Tuple> pqueue = new PriorityQueue<>();
        int n = matrix.length;
        for(int i = 0; i < n; i++){
            pqueue.offer(new Tuple(0, i, matrix[0][i]));
        }
        for(int i = 0; i < k - 1; i++){
            Tuple t = pqueue.poll();
            if(t.x == n - 1)
                continue;
            else{
                pqueue.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
            }
        }
        return pqueue.poll().val;
    }
}

class Tuple implements Comparable<Tuple>{
    int x;
    int y;
    int val;
    public Tuple(int x, int y, int val){
        this.x = x;
        this.y = y;
        this.val = val;
    }

    @Override
    public int compareTo(Tuple t){
        return this.val - t.val;
    }
}

Solution 2 : Binary Search

https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-clean-java-code/2

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi)
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0,  j = matrix[0].length - 1;
            for(int i = 0; i < matrix.length; i++) {
                while(j >= 0 && matrix[i][j] > mid) j--;
                count += (j + 1);
            }
            if(count < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}