Median of a Sorted Matrix in Kotlin

To find the median of a row-wise sorted matrix, we can follow the below steps:

Find the minimum and maximum elements in the matrix. We can do this by iterating through all the elements in the matrix and keeping track of the minimum and maximum values.
Use binary search to find the median value. We can do this by setting the low value to the minimum element and the high value to the maximum element. Then, we calculate the mid value as the average of low and high. We count the number of elements in the matrix that are less than or equal to the mid value. If the count is less than half the total number of elements in the matrix, we increase the low value to mid + 1. If the count is greater than half the total number of elements in the matrix, we decrease the high value to mid – 1. If the count is exactly half the total number of elements in the matrix, we return mid as the median.

Kotlin

fun findMedian(matrix: Array<IntArray>): Int {
    val rows = matrix.size
    val cols = matrix[0].size

    // Step 1: Find minimum and maximum elements
    var minElement = Int.MAX_VALUE
    var maxElement = Int.MIN_VALUE
    for (i in 0 until rows) {
        minElement = minOf(minElement, matrix[i][0])
        maxElement = maxOf(maxElement, matrix[i][cols - 1])
    }

    // Step 2: Use binary search to find median
    val targetCount = (rows * cols + 1) / 2
    var low = minElement
    var high = maxElement
    while (low < high) {
        val mid = (low + high) / 2
        var count = 0
        for (i in 0 until rows) {
            count += matrix[i].count { it <= mid }
        }
        if (count < targetCount) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    return low
}
fun main() {
    val matrix = arrayOf(
        intArrayOf(1, 3, 5),
        intArrayOf(2, 4, 6),
        intArrayOf(7, 8, 9)
    )
    val median = findMedian(matrix)
    println("Median: $median")
}

This function takes a 2D array matrix of integers as input and returns the median value as an integer. The function first finds the minimum and maximum elements in the matrix by iterating through all the rows. Then, it uses binary search to find the median value by setting the low and high values to the minimum and maximum elements, respectively, and iteratively narrowing the search range until the median is found. Finally, the function returns the median value.

main function creates a 3×3 row-wise sorted matrix and calls the findMedian function to find its median value. The median value should be 5, since there are 9 elements in the matrix and the middle element is 5. The function then prints the median value to the console. You can replace this example matrix with your own row-wise sorted matrix to find its median value.

Leave a Comment Cancel reply