0378. Kth Smallest Element in a Sorted Matrix

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

Description

Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example 1:

**Input:** matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
**Output:** 13
**Explanation:** The elements in the matrix are [1,5,9,10,11,12,13,**13**,15], and the 8th smallest number is 13

Example 2:

**Input:** matrix = [[-5]], k = 1
**Output:** -5

Constraints:

• n == matrix.length

• n == matrix[i].length

• 1 <= n <= 300

• -109 <= matrix[i][j] <= 109

• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.

• 1 <= k <= n2

ac1: minHeap

similar to: https://leetcode.com/problems/merge-k-sorted-lists/description/

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();


        // int[] node = new int[3];  // row, column, value
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {return a[2] - b[2];});
        for (int i = 0; i < matrix.length; i++) {
            pq.offer(new int[]{i, 0, matrix[i][0]});
        }

        // count
        int cnt = 0, res = 0;
        while (!pq.isEmpty()) {
            int[] h = pq.poll();
            cnt++;
            if (cnt == k) {
                res = h[2];
                break;
            } 
            h[1]++;  // move col pointer forward
            if (h[1] < matrix[h[0]].length) {  // if still in the range, put it back, otherwise discard it.
                h[2] = matrix[h[0]][h[1]];
                pq.offer(h);
            }
        }

        return res;
    }
}

// O(klogR) time, O(R) space

ac2: binary search

even so hard to understand.

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();

        int n = matrix.length;
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        int count = 0;
        while (l < r) {
            int mid = l + (r - l) / 2;
            count = countLessEqual(matrix, mid);
            if (count >= k) r = mid;
            else l = mid + 1;
        }

        return l;

    }
    // return count of those less or equal to target
    private int countLessEqual(int[][] matrix, int t) {
        int n = matrix.length;
        int res = 0;

        for (int r = 0; r < n; r++) {
            int c = 0;
            while (c < n && matrix[r][c] <= t) c++;
            res += c;
        }

        return res;
    }
}

// O(nlog(max-min)) time, O(1) space

another version, template

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();

        int n = matrix.length;
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        int count = 0;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            count = countLess(matrix, mid);
            if (count >= k) r = mid;
            else l = mid;
        }
        // compair last left, right
        if (countLess(matrix, r) <= k-1) return r;
        else return l;

    }
    // return count of those less target
    private int countLess(int[][] matrix, int t) {
        int n = matrix.length;
        int res = 0;

        for (int r = 0; r < n; r++) {
            int c = 0;
            while (c < n && matrix[r][c] < t) c++;
            res += c;
        }

        return res;
    }
}