We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Element in a Sorted Matrix

Difficulty: Medium

Problem Description

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k-th smallest element in the matrix. Note that it is the k-th smallest element in the sorted order, not the k-th distinct element.

Key Insights

  • The matrix is sorted both row-wise and column-wise.
  • The k-th smallest element can be found using a binary search approach on the value range of the matrix.
  • A min-heap (priority queue) can be employed to efficiently find the k-th smallest element by repeatedly extracting the smallest element.

Space and Time Complexity

Time Complexity: O(k log n) - where k is the number of elements to extract and n is the number of rows/columns. Space Complexity: O(n) - for the min-heap used to store elements.

Solution

To solve the problem, we can utilize a binary search approach combined with a counting mechanism that leverages the sorted property of the matrix. The algorithm involves:

  1. Defining the range of possible values (from the smallest element to the largest element in the matrix).
  2. Performing binary search on this range, where for each mid value, we count how many elements in the matrix are less than or equal to mid.
  3. If the count is less than k, we adjust the search range to higher values; otherwise, we adjust to lower values.
  4. The process continues until we narrow down to the k-th smallest element.

Alternatively, a min-heap can be used to store the smallest elements from the matrix until we reach the k-th extraction.

Code Solutions

import heapq

def kthSmallest(matrix, k):
    n = len(matrix)
    min_heap = []
    
    for i in range(min(n, k)):  # Only need to push the first k elements from each row
        heapq.heappush(min_heap, (matrix[i][0], i, 0))  # (value, row index, column index)

    count = 0
    while min_heap:
        value, row, col = heapq.heappop(min_heap)
        count += 1
        
        if count == k:
            return value
        
        if col + 1 < n:  # Push the next element in the same row
            heapq.heappush(min_heap, (matrix[row][col + 1], row, col + 1))
← Back to All Questions