378. Kth Smallest Element in a Sorted Matrix (Medium)
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find 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:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
Solutions
class Solution {
public int kthSmallest(int[][] matrix, int k) {
// corner case, matrix
if (matrix == null || matrix.length == 0) {
return -1;
}
int row = matrix.length;
// what if not nxn matrix, to make the solution more flexible, take column size into account.
int col = matrix[0].length;
// corner case k
if (k >= row * col) {
return matrix[row-1][col-1];
}
// keep track of the head pointer for each row in matrix
int[] headers = new int[row];
Arrays.fill(headers, 0);
// set a count for the visited values
int count = 0;
while (count < row * col) {
// Define smallest row id r, smallest col id c, and minimum value min
// Do not set it with the first row's in case the first row already searched through
// such that overstep the boundary.
int r = -1;
int c = -1;
int min = Integer.MAX_VALUE;
// go through the matrix row by row
for (int i = 0; i < row; i++) {
// all elements are scanned through, skip to next row
if (headers[i] >= col) {
continue;
}
// every time pick one smallest element from all the matrix rows
if (r == -1) {
r = i;
c = headers[i];
min = matrix[r][c];
continue;
}
if (min <= matrix[i][headers[i]]) {
continue;
}
r = i;
c = headers[i];
min = matrix[r][c];
}
// increase head pointer of row matrix[r]
headers[r]++;
count++;
// if count == k, return current value in matrix[r][c]
if (count == k) {
return matrix[r][c];
}
}
// Execution will never make it here.
return -1;
}
}