algoadvance

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

Example:

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

Output: 13

Note:

• You may assume k is always valid, 1 ≤ k ≤ n^2.

Clarifying Questions

1. Input Constraints:
   • What is the range of values for n?
   • Are all elements in the matrix distinct?
2. Output:
   • If there are multiple possible kth smallest elements (duplicates), should we return any specific one or the problem guarantees that there won’t be such cases?

Strategy

Heap Approach

1. Min-Heap:
   • Use a heap data structure to take advantage of its sorting properties.
   • Initially, insert the first element of each row into the heap keeping track of their positions.
   • Extract the minimum element from the heap k times.
   • Every time you extract the minimum element, if there is a next element in the same row, insert it into the heap.
2. Binary Search (Optimized Approach):
   • Utilize binary search over the range of the matrix elements.
   • Determine the mid value in the given range and count how many elements in the matrix are less than or equal to mid.
   • Adjust the search range based on the count.

Here, we will implement the Heap Approach using Python’s heapq library for brevity and ease of understanding.

Code

import heapq

def kthSmallest(matrix, k):
    n = len(matrix)
    min_heap = []
    
    # Initialize min heap with the first element from each row.
    for r in range(min(len(matrix), k)):  # Only need the first min(len(matrix), k)
        heapq.heappush(min_heap, (matrix[r][0], r, 0))
    
    # Extract min element from heap k times
    while k:
        element, r, c = heapq.heappop(min_heap)
        if c < n - 1:
            heapq.heappush(min_heap, (matrix[r][c+1], r, c+1))
        k -= 1
    
    return element

# Example usage:
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
]
k = 8
print(kthSmallest(matrix, k))  # Output should be 13

Time Complexity

• Initialization of Heap: O(min(k, n)) because we only consider the first element of each row.
• Extract min from Heap (k times): Each heap operation (pop/push) is O(log(min(k, n))). For k operations, it’s O(k * log(min(k, n))).
• Overall, the complexity is O(k * log(min(k, n))).

Space Complexity

• The heap can grow up to size min(k, n), so the space complexity is O(min(k, n)).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?