Finding the median of two sorted arrays seems straightforward at first glance. However, this problem challenges you to achieve logarithmic time complexity, making it a favorite in coding interviews. Let’s explore different approaches and work toward the most efficient solution.

Understanding the Problem

You receive two sorted arrays in ascending order and need to find the median of the combined array.

Mathematically, the median represents the middle element. For an odd number of elements, the median is the element at position (n+1)/2. For an even number of elements, the median is the average of the two middle elements at positions n/2 and (n/2)+1.

For example, with seven elements [1, 3, 5, 13, 17, 19, 23], the median is 13 at position 4. With eight elements [10, 20, 30, 40, 50, 60, 70, 80], the median is (40+50)/2 = 45.

The challenge: achieve O(\log(m+n)) time complexity without merging and sorting both arrays.

Approach 1: Brute Force Method

The most intuitive approach involves merging both arrays, sorting the result, and finding the median.

This method works correctly but isn’t efficient. Merging takes O(m+n) time, and sorting takes O((m+n) \log(m+n)) time. While this solves the problem, it doesn’t meet the logarithmic time requirement.

Time Complexity: O((m+n) \log(m+n))
Space Complexity: O(m+n)

Approach 2: Two Pointer Method

Since both arrays are already sorted, you can use two pointers to find the median without fully merging the arrays.

Start pointers at the beginning of both arrays. Compare elements and move the pointer pointing to the smaller value. Count elements until you reach the median position. For an odd total length, find the element at position (total+1)/2. For an even total length, find elements at positions total/2 and (total/2)+1, then calculate their average.

This approach eliminates the need for sorting. You only traverse until reaching the median position, which is approximately (m+n)/2 elements.

Time Complexity: O(m+n)
Space Complexity: O(1)

This solution works well for medium-difficulty problems, but interviews often require logarithmic time complexity.

Approach 3: Binary Search (Optimal Solution)

When logarithmic time complexity is required, binary search becomes the key. The insight: finding the median means finding a valid partition where all elements on the left are smaller than all elements on the right, and both sides have equal (or nearly equal) numbers of elements.

Understanding Partitions

A valid median partition satisfies two conditions:

1. Equal distribution: The left partition contains (total+1)/2 elements, and the right contains the remaining elements.
2. Ordering constraint: All elements in the left partition must be smaller than all elements in the right partition.

Once you fix a partition in one array, the partition in the second array is automatically determined. If you take x elements from the first array, you must take (total+1)/2 - x elements from the second array.

Validating a Partition

To validate a partition, check four key values:

• L1: Last element in the left partition of array 1
• R1: First element in the right partition of array 1
• L2: Last element in the left partition of array 2
• R2: First element in the right partition of array 2

The partition is valid if L1 \leq R2 and L2 \leq R1. Since both arrays are sorted, this ensures all left elements are smaller than all right elements.

Binary Search Implementation

Apply binary search on the smaller array to find the correct partition:

1. Set low = 0 and high = length of smaller array
2. Calculate mid = (low + high) / 2
3. Determine partition in the second array: partitionY = (total+1)/2 - partitionX
4. Calculate L1, R1, L2, R2
5. If L1 \leq R2 and L2 \leq R1, you found a valid partition
6. If L1 > R2, move high = mid - 1 (too many elements from first array)
7. If L2 > R1, move low = mid + 1 (too few elements from first array)

Once you find a valid partition, calculate the median:

• If total length is odd: median = \max(L1, L2)
• If total length is even: median = (\max(L1, L2) + \min(R1, R2)) / 2

Time Complexity: O(\log(\min(m, n)))
Space Complexity: O(1)

Why This Solution Works

Binary search works here because:

• Partitions follow a monotonic property: if a partition at position i is invalid, partitions at positions less than i (or greater than i, depending on the condition) are also invalid.
• You can eliminate half the search space in each iteration.
• The smaller array limits the search space, making the algorithm efficient.

This approach achieves the required logarithmic time complexity while using constant extra space.

---

If you need personalized guidance on solving this problem or preparing for coding interviews, you can schedule a one-on-one session to discuss your specific questions.

Super helpful resources: https://nikoo28.github.io/all-my-links/

Code:

double findMedianSortedArrays(int[] nums1, int[] nums2) {

    int[] smaller = nums1.length > nums2.length ? nums2 : nums1;
    int[] larger = nums1.length > nums2.length ? nums1 : nums2;
    int totalLength = nums1.length + nums2.length;

    int low = 0, high = smaller.length;

    while (low <= high) {
      int partitionX = (low + high) / 2;
      int partitionY = (totalLength + 1) / 2 - partitionX;

      int l1 = partitionX == 0 ? Integer.MIN_VALUE : smaller[partitionX - 1];
      int r1 = partitionX == smaller.length ? Integer.MAX_VALUE : smaller[partitionX];

      int l2 = partitionY == 0 ? Integer.MIN_VALUE : larger[partitionY - 1];
      int r2 = partitionY == larger.length ? Integer.MAX_VALUE : larger[partitionY];

      if (l1 <= r2 && l2 <= r1)
        // means this is a valid partition
        if ((totalLength) % 2 == 0)
          return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;
        else
          return Math.max(l1, l2);

      if (l1 > r2) high = partitionX - 1;
      else low = partitionX + 1;
    }

    return 0;
  }
Code language: Java (java)

Video Explanation

For a detailed walkthrough with visual examples and code implementation, check out the video explanation: