Kth Smallest Element in a Sorted Matrix

January 25, 2024

Problem Statement #

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Example:

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

Solution Approach #

The solution involves using a min heap to efficiently find the kth smallest element. Elements of the matrix are added to the heap, and then extracted until the kth element is reached.

Algorithm Steps #

1. Create a min heap.
2. Add the first element of each row to the heap.
3. Pop elements from the heap k times. Each time an element is popped, add the next element from the same row (if any) to the heap.
4. The kth popped element is the answer.

Code (Python) #

import heapq

def kthSmallest(matrix, k):
    n = len(matrix)
    min_heap = [(matrix[i][0], i, 0) for i in range(n)]  # (value, row, col)
    heapq.heapify(min_heap)

    for _ in range(k - 1):
        val, r, c = heapq.heappop(min_heap)
        if c < n - 1:
            heapq.heappush(min_heap, (matrix[r][c + 1], r, c + 1))

    return heapq.heappop(min_heap)[0]

# Test the function
print(kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8))  # Output: 13

Time Complexity #

O(k log n), where n is the number of rows (or columns) in the matrix. The log n factor is due to heap operations.

Space Complexity #

O(n), for the heap.