Problems

Median of 2 arrays

Problem Statement: Given two sorted arrays each containing n elements. Find the median of the union of two arrays

Approach:
Merging them and finding the median takes O(n). But we can solve this O(log n).

Let medianA and medianB be median of 2 arrays. If medianA == medianB, then it is the overall median. Otherwise, median of the union must be between medianA and medianB.

fun findUnionMedian(a1: IntArray, a2: IntArray) {
    val m = a1.size
    val n = a2.size
    var l = 0
    var r = m

    while(l <= r) {
        val i = (l + r) / 2
        val j = (m + n - 1) / 2 - i

        val a1L = if(i == 0) Int.MIN_VALUE else a1[i - 1]
        val a1R = if(i == m) Int.MAX_VALUE else a1[i]
        val a2L = if(j == 0) Int.MIN_VALUE else a2[i - 1]
        val a2R = if(j == n) Int.MAX_VALUE else a2[i]

        if(a1L <= a2R && a2L <= a1R) {
            return if((m+n) %2 == 0) {
                (maxOf(a1L, a2L) + minOf(a1R, a2R)) / 2
            } else maxof(a1L, a2L)
        } else if(a1L > a2R) {
            r = i - 1
        } else l = i + 1
    }
}

---

\(k^{th}\) smallest of 2 arrays

Problem Statement: Given two sorted arrays find the \(k^{th}\) smallest element of union of two arrays

Approach:
Similar to the above problem

---

Problem Statement:

Approach:

---