Kth smallest element in a sorted matrix problem in c#

Programming C#
1

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

  1. Data Structure:

    • The matrix is represented as a jagged array (int[][]), and a SortedSet is used as a min-heap to keep track of the current candidates for the Kth smallest element.

  2. 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.

  3. 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.

  4. Final Result:

    • After k-1 iterations, the Kth smallest element is the smallest element in the heap. We return its value.

  5. Main Method:

    • In the Main method, we define a sample matrix and a value for k, then call the KthSmallest method and print the result.

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.