Kth Smallest Element In A Sorted Matrix - Leetcode Solution

Problem Statement:

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

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

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

Example 2: Input: matrix = [[-5]], k = 1 Output: -5

Approach: We can solve the problem by using a heap, where we need to add the first element of the each row in the heap. After adding k elements to the heap if any other element is less than the root of the heap, then we will pop the root and push the new element to the heap. In this way, we keep the heap sorted in ascending order and at the end, the kth smallest element will be at the root of the heap.

Algorithm:

1. Create a min heap to store the elements of the matrix.
2. Add the first element of each row of the matrix to the heap along with the row index and column index of the element.
3. Repeat the following steps k times: a. Extract the minimum element from the heap along with the row and column indices. b. If the current element is not the last element of the row, add the next element of that row to the heap.
4. Return the value of the kth smallest element which is at the root of the heap.

Code:

import heapq

def kthSmallest(matrix, k):
    n = len(matrix)
    heap = []
    
    # Add first element of each row to the heap with row index and column index
    for i in range(n):
        heapq.heappush(heap, (matrix[i][0], i, 0))
        
    # Extract k elements from the heap
    for i in range(k):
        element, row, col = heapq.heappop(heap)
        if col < n-1:
            heapq.heappush(heap, (matrix[row][col+1], row, col+1))
    return element

Complexity Analysis:

Time Complexity: O(k log n). We need to add k elements to the heap and extract k elements from the heap. Adding an element to the heap takes O(log n) time and extracting the minimum element from the heap takes O(log n) time. Therefore, the overall time complexity is O(k log n).

Space Complexity: O(n). We need to store at most n elements in the heap. Therefore, the overall space complexity is O(n).

1