Practice/Amazon/Leetcode 378. Kth Smallest Element in a Sorted Matrix

Leetcode 378. Kth Smallest Element in a Sorted Matrix

CodingMust

Problem

You are given an n × n matrix where each row is sorted in ascending order from left to right, and each column is also sorted in ascending order from top to bottom. Your task is to find the kth smallest element in this matrix.

Note that we are looking for the kth smallest element in sorted order, not the kth distinct element. If there are duplicate values, they should each be counted separately.

Requirements

1. Return the kth smallest element when all matrix elements are considered in sorted order
2. Handle duplicate values correctly (count each occurrence separately)
3. Take advantage of the sorted property to achieve better than O(n²) time complexity
4. The matrix dimensions are n × n where n is the length of each side

Constraints

• n == matrix.length == matrix[i].length
• 1 ≤ n ≤ 300
• -10⁹ ≤ matrix[i][j] ≤ 10⁹
• All rows and columns are sorted in non-decreasing order
• 1 ≤ k ≤ n²

Examples

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in sorted order are [1,5,9,10,11,12,13,13,15]. The 8th smallest element is 13.

Example 2:

Input: matrix = [[1,2],[1,3]], k = 2 Output: 1 Explanation: The elements in sorted order are [1,1,2,3]. The 2nd smallest element is 1 (the duplicate).

Example 3:

Input: matrix = [[-5]], k = 1 Output: -5 Explanation: Single element matrix.