Median of Two Sorted Arrays - Video Solutions

Problem Overview: You are given two sorted arrays of sizes m and n. The goal is to compute the median of the combined sorted sequence without explicitly building the full merged array.

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

This approach simulates the merge step from merge sort. Use two pointers to iterate through both arrays in sorted order until you reach the middle element of the combined length. If the total length is odd, the median is the middle value. If it is even, the median is the average of the two middle values. The idea is simple and reliable because both arrays are already sorted, but the algorithm still scans up to m + n elements.

This solution is useful when constraints are small or when you want a quick implementation during practice. It relies on sequential iteration over arrays and does not use advanced optimization.

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

The optimal solution treats the problem as a partitioning task. Instead of merging arrays, perform binary search on the smaller array to find a partition such that the left halves of both arrays contain exactly half of the total elements. The key condition: the maximum element on the left side must be less than or equal to the minimum element on the right side.

During each step, choose a partition index in the smaller array and compute the corresponding partition in the second array. Check boundary values around the partitions. If the ordering condition fails, move the binary search window left or right. Once the correct partition is found, compute the median using the boundary elements.

This technique uses properties of sorted arrays and reduces the search space logarithmically. It combines ideas from arrays, binary search, and divide and conquer to achieve optimal performance.

Recommended for interviews: Interviewers typically expect the binary search partition solution with O(log(min(m,n))) time complexity. The merge approach demonstrates baseline understanding, but the partition method shows strong algorithmic reasoning and comfort with binary search edge cases.