Kth Smallest Element in a Row-Column Wise Sorted Matrix

Understanding the Problem

The goal is to find the Kth smallest element in a matrix that is sorted row-wise and column-wise.

Method 1: Using a Combined Array

This method combines all elements into a single array and then sorts it.

def kth_smallest(matrix, k):
    combined = []

    # Combine all elements into a single array
    for row in matrix:
        combined.extend(row)

    # Sort the combined array
    combined.sort()

    # Return the Kth smallest element
    return combined[k - 1]

# Example usage
matrix = [
    [10, 20, 30],
    [15, 25, 35],
    [27, 29, 37],
    [32, 33, 38]
]
k = 5
print("Kth smallest element:", kth_smallest(matrix, k))
            

Output:

Kth smallest element: 25

Method 2: Using Min-Heap

This method uses a min-heap to find the Kth smallest element efficiently.

import heapq

def kth_smallest(matrix, k):
    min_heap = []

    # Push the first element of each row into the min-heap
    for row in matrix:
        heapq.heappush(min_heap, (row[0], 0, 0))  # (value, row, column)

    current = None
    for _ in range(k):
        current = heapq.heappop(min_heap)

        # If there is a next element in the same row, push it into the heap
        if current[1] + 1 < len(matrix[0]):
            heapq.heappush(min_heap, (matrix[current[0]][current[1] + 1], current[0], current[1] + 1))

    return current[0]  # The Kth smallest element

# Example usage
matrix = [
    [10, 20, 30],
    [15, 25, 35],
    [27, 29, 37],
    [32, 33, 38]
]
k = 5
print("Kth smallest element:", kth_smallest(matrix, k))
            

Output:

Kth smallest element: 25

Method 3: Using Binary Search

This method uses binary search to find the Kth smallest element.

def count_less_equal(matrix, mid):
    count = 0
    row = len(matrix) - 1
    col = 0

    while row >= 0 and col < len(matrix[0]):
        if matrix[row][col] <= mid:
            count += (row + 1)  # All elements in this row are <= mid
            col += 1
        else:
            row -= 1
    return count

def kth_smallest(matrix, k):
    low = matrix[0][0]
    high = matrix[-1][-1]

    while low < high:
        mid = low + (high - low) // 2
        if count_less_equal(matrix, mid) < k:
            low = mid + 1
        else:
            high = mid

    return low  # The Kth smallest element

# Example usage
matrix = [
    [10, 20, 30],
    [15, 25, 35],
    [27, 29, 37],
    [32, 33, 38]
]
k = 5
print("Kth smallest element:", kth_smallest(matrix, k))
            

Output:

Kth smallest element: 25