#378

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Kth Smallest Element in a Sorted Matrix

Find the kth smallest element in a sorted n x n matrix using efficient binary search or heap strategies for optimized memory usage.

array binary search sorting heap priority queue matrix

Problem Statement

Given an n x n matrix where each row and each column is sorted in ascending order, identify the kth smallest element considering the full sorted order. The element to return is based on the sorted position, not uniqueness, and must be computed efficiently without storing all matrix elements.

Implement a function that takes an n x n sorted matrix and an integer k, and returns the kth smallest element. Solutions should optimize memory beyond O(n^2), handling matrices up to size 300x300 with elements ranging from -10^9 to 10^9, ensuring correct counting even when duplicates exist.

Examples

Example 1

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output: 13

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

Example details omitted.

Constraints

n == matrix.length == 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

Solution Approach

Binary Search Over Value Range

Use the smallest and largest matrix elements as low and high bounds. Perform binary search on this range, counting elements less than or equal to the mid-value at each step. Narrow the bounds until the kth smallest element is identified. This pattern avoids full sorting and optimizes memory usage.

Min-Heap Traversal

Initialize a min-heap with the first element of each row. Repeatedly pop the smallest element and push the next element from the same row until k elements are popped. This approach ensures the kth smallest is extracted without flattening the matrix, directly reflecting the problem's priority queue pattern.

Counting Function Optimization

Implement a helper function to count elements less than or equal to a given target using row-wise iteration from bottom-left or top-right. This counting informs the binary search decision efficiently, leveraging the matrix's sorted properties to avoid unnecessary traversal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Binary search approach has O(n log(max-min)) time, where max and min are the matrix extremes, and O(1) space. Min-heap method requires O(k log n) time and O(n) space for the heap. Counting function optimizes the binary search by avoiding full matrix flattening, reducing runtime significantly for large n.

What Interviewers Usually Probe

Asks how to improve from O(n^2) memory to O(n) using matrix properties.
Probes whether you can count elements without flattening the matrix.
Checks if binary search on values versus indices is understood and correctly implemented.

Common Pitfalls or Variants

Common pitfalls

Flattening the matrix and sorting uses excessive memory and ignores constraints.
Miscounting elements when duplicates exist, which can return the wrong kth element.
Confusing kth smallest with kth distinct element, leading to incorrect output.

Follow-up variants

Find the kth largest element in a sorted matrix using similar binary search logic.
Handle rectangular matrices where rows and columns are sorted differently.
Adapt heap solution to track positions in multiple sorted arrays or merged lists.

FAQ

What is the best approach for Kth Smallest Element in a Sorted Matrix?

Use binary search over the value range with a counting function or a min-heap traversal for efficient memory usage.

Can duplicates affect the kth smallest element solution?

Yes, duplicates require careful counting to ensure the kth smallest in sorted order is correct, not just distinct elements.

What is the space complexity of the binary search method?

Binary search requires O(1) extra space beyond the input, leveraging the matrix's inherent sorted structure.

Is flattening the matrix a recommended strategy?

No, flattening uses O(n^2) memory and ignores constraints; optimized binary search or heap methods are preferred.

How does GhostInterview help with the binary search pattern?

It provides guided counting functions, boundary setup, and iterative narrowing steps tailored to sorted matrices, reducing errors and runtime.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        def check(matrix, mid, k, n):
            count = 0
            i, j = n - 1, 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    count += i + 1
                    j += 1
                else:
                    i -= 1
            return count >= k

        n = len(matrix)
        left, right = matrix[0][0], matrix[n - 1][n - 1]
        while left < right:
            mid = (left + right) >> 1
            if check(matrix, mid, k, n):
                right = mid
            else:
                left = mid + 1
        return left

Continue Practicing

#658 find k closest elements #778 swim in rising water #786 k th smallest prime fraction