Median of Two Sorted Arrays - Solution & Explanation

Problem Overview: You receive two individually sorted arrays and must return the median of the combined dataset. The challenge is computing the median without actually merging both arrays, ideally faster than linear time.

Approach 1: Merge and Find Median (O(m + n) time, O(1) space)

The straightforward approach simulates the merge step of merge sort. Use two pointers, one for each array, and iterate through elements in sorted order. Track the element positions until you reach the median index (or the two middle indices when the total length is even). Since the arrays are already sorted, each step only compares the current values and advances one pointer.

This approach runs in O(m + n) time because you may scan both arrays entirely. Space can remain O(1) if you avoid building a merged array and instead only track the current and previous values. It’s easy to implement and useful for understanding the problem mechanics, but it does not meet the strict O(log(m+n)) expectation many interviewers want for this problem.

Approach 2: Binary Search on Smaller Array (O(log(min(m,n))) time, O(1) space)

The optimal solution uses binary search to partition the arrays so that the left half contains exactly half the elements of the combined arrays. Perform binary search on the smaller array and choose a partition index. The corresponding partition in the second array is derived from the total elements required on the left side.

The key condition: every element on the left side must be less than or equal to every element on the right side. Check this by comparing boundary values around both partitions. If the condition fails, adjust the partition using binary search. Once valid partitions are found, compute the median from the boundary elements depending on whether the total length is odd or even.

This technique leverages the sorted property of the arrays and turns the problem into a partition search problem. The runtime becomes O(log(min(m,n))) with constant space, making it one of the classic advanced applications of arrays, binary search, and divide and conquer.

Recommended for interviews: Interviewers usually expect the binary search partition method because it achieves logarithmic complexity and demonstrates strong algorithmic reasoning. The merge approach shows correct understanding of medians and sorted traversal, but the binary search solution shows deeper skill with partition logic and edge-case handling.