Vibed to Cracked
Sign In
Google Questions

Given two sorted arrays, find the median of the combined sorted array in O(log(min(n,m))) time.

MediumTechnicalAlgorithms25-30 minutes

Model Answer

This is one of the hardest classic interview problems. The key insight is that finding a median is equivalent to finding a partition where all elements on the left side are smaller than all elements on the right side. We binary search on the shorter array to find the correct partition point. If the shorter array has n elements, we need to place i elements from it on the left side, and (n+m+1)/2 - i elements from the longer array. At a valid partition: max(left side) <= min(right side).

Approaches

Binary Search on Partition

Binary search on the shorter array's partition point. At each step, check if the partition is valid (all left elements <= all right elements). Adjust search based on which side is imbalanced.

function findMedian(nums1, nums2) {
  // Ensure nums1 is the shorter array
  if (nums1.length > nums2.length) return findMedian(nums2, nums1);

  const n = nums1.length, m = nums2.length;
  let low = 0, high = n;

  while (low <= high) {
    const i = Math.floor((low + high) / 2); // partition in nums1
    const j = Math.floor((n + m + 1) / 2) - i; // partition in nums2

    const left1 = i === 0 ? -Infinity : nums1[i - 1];
    const right1 = i === n ? Infinity : nums1[i];
    const left2 = j === 0 ? -Infinity : nums2[j - 1];
    const right2 = j === m ? Infinity : nums2[j];

    if (left1 <= right2 && left2 <= right1) {
      // Valid partition found
      if ((n + m) % 2 === 1) return Math.max(left1, left2);
      return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
    } else if (left1 > right2) {
      high = i - 1;
    } else {
      low = i + 1;
    }
  }
}
Time: O(log(min(n, m)))Space: O(1)

Common Mistakes

  • 1.Merging the arrays (O(n+m)) instead of using binary search
  • 2.Not ensuring binary search runs on the shorter array
  • 3.Off-by-one errors in partition index calculation
  • 4.Not handling the case where one partition is at the extreme edge (0 or length)

Follow-up Questions

  • What if one of the arrays is empty?
  • Can you extend this to find the k-th smallest element?
  • How would you handle this if the arrays could have duplicates?