Median of two Sorted Array in Kotlin

by

To find the median of two sorted arrays, we can use the divide and conquer strategy to divide the problem into smaller subproblems that can be solved recursively. Here’s a high-level algorithm to find the median of two sorted arrays nums1 and nums2:

  1. Determine the lengths of the two arrays n and m.
  2. If n > m, swap nums1 and nums2, and swap n and m.
  3. Compute the middle index mid of the merged array nums1 + nums2 using the formula (n + m) / 2.
  4. Use binary search to find the position pos1 of the middle element of nums1 such that nums1[pos1] is the last element that should be included in the left half of the merged array. We can use the fact that both arrays are sorted to perform the binary search in O(log n) time.
  5. Compute the position pos2 of the middle element of nums2 such that nums2[pos2] is the last element that should be included in the left half of the merged array. This can be computed as mid - pos1.
  6. Compute the values of leftMax and rightMin as follows:
    • If pos1 == 0, set leftMax to -INF.
    • Else, set leftMax to max(nums1[pos1 - 1], nums2[pos2 - 1]).
    • If pos1 == n, set rightMin to +INF.
    • Else, set rightMin to min(nums1[pos1], nums2[pos2]).
  7. If (n + m) % 2 == 0, return the average of leftMax and rightMin. Otherwise, return rightMin.

Here’s a Kotlin code that implements the above algorithm:

Kotlin
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    val m = nums1.size
    val n = nums2.size
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1) // swap to ensure nums1 is the shorter array
    }
    var low = 0
    var high = m
    while (low <= high) {
        val partitionX = (low + high) / 2
        val partitionY = (m + n + 1) / 2 - partitionX
        
        val maxLeftX = if (partitionX == 0) Int.MIN_VALUE else nums1[partitionX - 1]
        val minRightX = if (partitionX == m) Int.MAX_VALUE else nums1[partitionX]
        
        val maxLeftY = if (partitionY == 0) Int.MIN_VALUE else nums2[partitionY - 1]
        val minRightY = if (partitionY == n) Int.MAX_VALUE else nums2[partitionY]
        
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((m + n) % 2 == 0) {
                return (maxOf(maxLeftX, maxLeftY) + minOf(minRightX, minRightY)) / 2.0
            } else {
                return maxOf(maxLeftX, maxLeftY).toDouble()
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1
        } else {
            low = partitionX + 1
        }
    }
    throw IllegalArgumentException("Invalid input arrays")
}
fun main() {
    val nums1 = intArrayOf(1, 3)
    val nums2 = intArrayOf(2, 4, 5)
    val median = findMedianSortedArrays(nums1, nums2)
    println("Median of the two arrays is: $median")
}

Here’s a step-by-step explanation of how this function works:

  1. The findMedianSortedArrays function takes two sorted integer arrays, nums1 and nums2, as input and returns the median of the combined array. The function first determines the lengths of the two input arrays m and n. If m is greater than n, the function swaps the two arrays to ensure that nums1 is the shorter array.
  2. The function then initializes two variables low and high to partition the shorter array, nums1. A while loop is used to iteratively adjust the partition until the correct partitions are found. At each iteration, the midpoint of the partition is determined for the shorter array, partitionX, and the corresponding midpoint for the longer array, partitionY, is computed.
  3. Next, the function determines the left and right elements of the two partitions, maxLeftX, minRightX, maxLeftY, and minRightY, which represent the largest element in the left partition of nums1, the smallest element in the right partition of nums1, the largest element in the left partition of nums2, and the smallest element in the right partition of nums2.
  4. The function then checks if the correct partitions have been found by comparing the maximum left element of nums1 with the minimum right element of nums2 and the maximum left element of nums2 with the minimum right element of nums1. If the correct partitions are found, the function returns the median of the combined array, which is either the average of the two middle elements or the larger of the two middle elements depending on whether the combined array has an even or odd number of elements.
  5. If the correct partitions are not found, the function adjusts the partition by either searching in the left half or the right half of the shorter array, depending on the relative size of the maximum left element of nums1 and the minimum right element of nums2.
  6. The function returns an error message if the input arrays are invalid and do not contain any elements.

This function works by using binary search to find the correct partition of the two arrays. The median of the two arrays can be found once the correct partition has been found.

The time complexity of this function is O(log(min(m,n))), where m and n are the lengths of the two arrays. The space complexity is O(1), since we are not using any extra memory beyond a few variables to keep track of the indices and values in the arrays.

Leave a Comment