Package g0301_0400.s0378_kth_smallest_element_in_a_sorted_matrix

Class Solution

java.lang.Object

g0301_0400.s0378_kth_smallest_element_in_a_sorted_matrix.Solution

public class Solution
extends Object

378 - Kth Smallest Element in a Sorted Matrix.<p>Medium</p> <p>Given an <code>n x n</code> <code>matrix</code> where each of the rows and columns is sorted in ascending order, return <em>the</em> <code>k^th</code> <em>smallest element in the matrix</em>.</p> <p>Note that it is the <code>k^th</code> smallest element <strong>in the sorted order</strong> , not the <code>k^th</code> <strong>distinct</strong> element.</p> <p>You must find a solution with a memory complexity better than <code>O(n²)</code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8</p> <p><strong>Output:</strong> 13</p> <p><strong>Explanation:</strong> The elements in the matrix are [1,5,9,10,11,12,13, <strong>13</strong> ,15], and the 8^th smallest number is 13</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> matrix = [[-5]], k = 1</p> <p><strong>Output:</strong> -5</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == matrix.length == matrix[i].length</code></li> <li><code>1 <= n <= 300</code></li> <li><code>-10⁹ <= matrix[i][j] <= 10⁹</code></li> <li>All the rows and columns of <code>matrix</code> are <strong>guaranteed</strong> to be sorted in <strong>non-decreasing order</strong>.</li> <li><code>1 <= k <= n²</code></li> </ul> <p><strong>Follow up:</strong></p> <ul> <li>Could you solve the problem with a constant memory (i.e., <code>O(1)</code> memory complexity)?</li> <li>Could you solve the problem in <code>O(n)</code> 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="_top">this paper</a> fun.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	kthSmallest(int[][] matrix, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

kthSmallest

public int kthSmallest(int[][] matrix,
 int k)