378. Kth Smallest Element in a Sorted Matrix Medium

1/**
2 * [378] Kth Smallest Element in a Sorted Matrix
3 *
4 * Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k^th smallest element in the matrix.
5 * Note that it is the k^th smallest element in the sorted order, not the k^th distinct element.
6 * You must find a solution with a memory complexity better than O(n^2).
7 *  
8 * Example 1:
9 * 
10 * Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
11 * Output: 13
12 * Explanation: The elements in the matrix are [1,5,9,10,11,12,13,<u>13</u>,15], and the 8^th smallest number is 13
13 * 
14 * Example 2:
15 * 
16 * Input: matrix = [[-5]], k = 1
17 * Output: -5
18 * 
19 *  
20 * Constraints:
21 * 
22 * 	n == matrix.length == matrix[i].length
23 * 	1 <= n <= 300
24 * 	-10^9 <= matrix[i][j] <= 10^9
25 * 	All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
26 * 	1 <= k <= n^2
27 * 
28 *  
29 * Follow up:
30 * 
31 * 	Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
32 * 	Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading <a href="http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf" target="_blank">this paper</a> fun.
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
38// discuss: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn kth_smallest(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_378() {
56    }
57}
58