Median of Two Sorted Arrays

Median of Two Sorted Arrays

What is this problem about?

The "Median of Two Sorted Arrays" interview question asks you to find the median of two sorted arrays, nums1 and nums2, given that their total length is m + n. The challenge is to achieve this in an optimal time complexity, typically O(log(m+n)). This problem doesn't require merging the arrays explicitly. Instead, it tests your ability to find the k-th smallest element in two sorted arrays, which is a generalized version of finding the median. The median is simply the (m+n)/2-th or ((m+n)/2)-th and ((m+n)/2)+1-th smallest element(s), depending on whether the total length is odd or even.

Why is this asked in interviews?

This "Median of Two Sorted Arrays" coding problem is a very common and highly-regarded question in technical interviews at top-tier companies like Apple, Google, and Amazon. Its popularity stems from its ability to assess a candidate's mastery of fundamental algorithms, specifically Binary Search and Divide and Conquer. Interviewers use this problem to distinguish candidates who can apply these advanced techniques to complex scenarios, not just basic sorted arrays. It requires careful thought about edge cases, array partitioning, and recursive logic, making it an excellent benchmark for problem-solving skills and algorithmic creativity.

Algorithmic pattern used

The primary algorithmic pattern for the "Median of Two Sorted Arrays" interview question is Binary Search combined with a Divide and Conquer strategy. The core idea is to find the k-th smallest element in the combined sorted arrays. This can be done by strategically comparing the middle elements of partitioned sections of the two arrays. In each step, you eliminate half of the remaining search space. For finding the median, if the total length m+n is odd, you find the ((m+n)/2) + 1-th smallest element. If m+n is even, you find both the (m+n)/2-th and ((m+n)/2) + 1-th smallest elements and average them. This recursive partitioning ensures a logarithmic time complexity.

Example explanation

Let nums1 = [1, 3] and nums2 = [2]. Total elements m+n = 3 (odd). The median is the (3/2) + 1 = 2-nd smallest element. Let k = 2. We want to find the 2nd smallest element.

Step 1: Consider nums1 = [1, 3], nums2 = [2]. We need the 2nd smallest. Mid-point of nums1 (effectively 1 element, 1): nums1[0] = 1. Mid-point of nums2 (effectively 1 element, 2): nums2[0] = 2. Since 1 < 2, the 1st smallest element is from nums1. We eliminate nums1[0] and reduce k by 1. New nums1 = [3], nums2 = [2], k = 1.

Step 2: We need the 1st smallest element. Mid-point of nums1 (3): nums1[0] = 3. Mid-point of nums2 (2): nums2[0] = 2. Since 2 < 3, the 1st smallest element is from nums2. We eliminate nums2[0] and reduce k by 1. New nums1 = [3], nums2 = [], k = 0.

Since k is 0, we have found the element before the current step, which was 2. The 2nd smallest element is 2. So the median is 2.

Consider nums1 = [1, 2] and nums2 = [3, 4]. Total elements m+n = 4 (even). The median is (4/2)-th and (4/2)+1-th smallest, i.e., 2nd and 3rd smallest. Let's find the 2nd smallest and 3rd smallest using the k-th element logic. 2nd smallest: 2 3rd smallest: 3 Median is (2+3)/2 = 2.5.

Common mistakes candidates make

A common mistake in the "Median of Two Sorted Arrays" interview question is attempting to merge the arrays first, which takes O(m+n) time and space, defeating the logarithmic complexity requirement. Another frequent error is incorrect handling of edge cases, such as one array being empty, or reaching the end of one array during the partition process. Incorrectly calculating k or the partition points, especially when dealing with odd vs. even total lengths, can also lead to wrong answers. Many candidates struggle to correctly implement the recursive logic or the binary search boundaries, making the solution prone to off-by-one errors.

Interview preparation tip

To conquer the Median of Two Sorted Arrays coding problem, deeply understand Binary Search on the Answer. Focus on the find_kth_element helper function. Practice the logic of partitioning the arrays into left and right halves such that k elements are on the left. Pay special attention to how you compare nums1[k/2 - 1] and nums2[k/2 - 1] and then eliminate a portion of one array. Work through various examples, including empty arrays and arrays of different lengths, tracing the partitions and k value updates. Mastering this generalized k-th element finding is key to solving this problem efficiently.