Median of two sorted arrays

Time: O(log(min(n,m)))

Space: O(1)

Intuition

Binary search on the smaller array. Partition both arrays such that left half has (m+n)/2 elements and max(left) â‰¤ min(right).

Algorithm

1Ensure len(A) â‰¤ len(B). Binary search on A: lo=0, hi=len(A).
2partA=mid, partB=(m+n+1)/2 - partA.
3Check: maxLeftA â‰¤ minRightB and maxLeftB â‰¤ minRightA.
4If valid: median = max(maxLeft) for odd total, or (max(maxLeft)+min(minRight))/2 for even.

Common Pitfalls

•Use Â±infinity for boundary partitions (partA=0 or partA=len). Ensure binary search on shorter array.

Median of two sorted arrays.java

Java

// Approach: Binary search on the smaller array. Partition both arrays so left halves have total (n+m+1)/2 elements.
// Time: O(log(min(n,m))) Space: O(1)
class Solution {
    public int sumOfMiddleElements(int[] arr1, int[] arr2) {
        int n = arr1.length + arr2.length;

        return kthElement(n / 2, arr1, arr2) + kthElement((n / 2) + 1, arr1, arr2);
    }

    private int kthElement(int k, int[] arr1, int[] arr2) {
        int n = arr1.length;
        int m = arr2.length;

        if (n < m)
            return kthElement(k, arr2, arr1);

        int low = Math.max(0, k - m), high = Math.min(n, k);

        while (low <= high) {
            int cut1 = (low + high) / 2;
            int cut2 = k - cut1;

            int l1 = cut1 == 0 ? Integer.MIN_VALUE : arr1[cut1 - 1];
            int l2 = cut2 == 0 ? Integer.MIN_VALUE : arr2[cut2 - 1];

            int r1 = cut1 == n ? Integer.MAX_VALUE : arr1[cut1];
            int r2 = cut2 == m ? Integer.MAX_VALUE : arr2[cut2];

            if (l1 <= r1 && l2 <= r2)
                return Math.max(l1, l2);
            else if (l1 > l2)
                high = cut1 - 1;
            else
                low = cut1 + 1;
        }

        return 0;
    }
}

Was this solution helpful?