Median of two sorted arrays

JavaView on GFG

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

Space: O(1)

Problem Overview

Binary search on the smaller array.

See our study guide for structured GFG and LeetCode practice.

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?