Finding the Kth smallest element in a sorted matrix involves dealing with a matrix where each row and each column is sorted in ascending order. The challenge is to efficiently retrieve the Kth smallest element without having to sort the entire matrix.
Problem Statement
Given an n x n
matrix where each row and column is sorted, and an integer k
, find the Kth smallest element in the matrix.
C# Implementation
Here’s an implementation using a min-heap (priority queue) approach to efficiently find the Kth smallest element:
using System;
using System.Collections.Generic;
public class KthSmallestElementFinder
{
public static int KthSmallest(int[][] matrix, int k)
{
int n = matrix.Length;
// Min-heap to store the current candidates for the Kth smallest element
SortedSet<(int value, int row, int col)> minHeap = new SortedSet<(int, int, int)>();
// Initialize the min-heap with the first element of each row
for (int i = 0; i < Math.Min(n, k); i++)
{
minHeap.Add((matrix[i][0], i, 0));
}
// Extract the smallest element k times
for (int i = 0; i < k - 1; i++)
{
var (value, row, col) = minHeap.Min; // Get the smallest element
minHeap.Remove(minHeap.Min); // Remove it from the heap
// If there's a next element in the same row, add it to the heap
if (col + 1 < n)
{
minHeap.Add((matrix[row][col + 1], row, col + 1));
}
}
// The Kth smallest element will be at the top of the min-heap
return minHeap.Min.value;
}
public static void Main(string[] args)
{
int[][] matrix = new int[][]
{
new int[] { 1, 5, 9 },
new int[] { 10, 11, 13 },
new int[] { 12, 13, 15 }
};
int k = 8;
int result = KthSmallest(matrix, k);
Console.WriteLine($"The {k}th smallest element is: {result}");
}
}
Explanation
-
Data Structure:
- The matrix is represented as a jagged array (
int[][]
), and aSortedSet
is used as a min-heap to keep track of the current candidates for the Kth smallest element.
- The matrix is represented as a jagged array (
-
Initialization:
- The number of rows in the matrix is stored in
n
. - The min-heap is initialized with the first element of each row. This is done only for the first
k
rows to ensure we don’t insert more than needed.
- The number of rows in the matrix is stored in
-
Finding the Kth Smallest Element:
- We loop
k-1
times to extract the smallest element from the heap. - After extracting the smallest element, we check if there are more elements in the same row (i.e., the next column). If so, we add that next element to the heap.
- We loop
-
Final Result:
- After
k-1
iterations, the Kth smallest element is the smallest element in the heap. We return its value.
- After
-
Main Method:
- In the
Main
method, we define a sample matrix and a value fork
, then call theKthSmallest
method and print the result.
- In the
Complexity Analysis
- The time complexity of this approach is (O(k \log \text{min}(n, k))), where (n) is the number of rows (and columns) in the matrix. This is due to the fact that we perform (O(k)) extractions and insertions into the min-heap, which has a logarithmic complexity.
- The space complexity is (O(\min(n, k))) for the heap storage.
Usage
You can modify the matrix
and k
values in the Main
method to test different scenarios. This implementation efficiently finds the Kth smallest element in a sorted matrix using a min-heap, ensuring good performance even for larger matrices.