The “Median of Two Sorted Arrays” problem is a classic and tricky coding interview question. It tests your understanding of merging, searching, and partitioning arrays. <\/p>\n\n\n\n
In this blog, we\u2019ll explain the problem, walk you through brute force, better, and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Given two sorted arrays The overall run time complexity should be Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n How does this solution work?<\/strong><\/p>\n\n\n\n Why does this work?<\/strong> When should you use this?<\/strong>
\n\n\n\nProblem Statement<\/strong><\/h2>\n\n\n\n
nums1<\/code> and nums2<\/code> of size m<\/code> and n<\/code> respectively, return the median<\/strong> of the two sorted arrays.<\/p>\n\n\n\nO(log (m+n))<\/code>.<\/p>\n\n\n\nInput:<\/strong> nums1 = [1,3], nums2 = [2]
Output:<\/strong> 2.00000
Explanation:<\/strong> merged array = [1,2,3] and median is 2.<\/pre>\n\n\n\nInput:<\/strong> nums1 = [1,2], nums2 = [3,4]
Output:<\/strong> 2.50000
Explanation:<\/strong> merged array = [1,2,3,4] and median is (2 + 3) \/ 2 = 2.5.<\/pre>\n\n\n\n\n
nums1.length == m<\/code><\/li>\n\n\n\nnums2.length == n<\/code><\/li>\n\n\n\n0 <= m <= 1000<\/code><\/li>\n\n\n\n0 <= n <= 1000<\/code><\/li>\n\n\n\n1 <= m + n <= 2000<\/code><\/li>\n\n\n\n-106<\/sup> <= nums1[i], nums2[i] <= 106<\/sup><\/code><\/li>\n<\/ul>\n\n\n
\n\n\n\nBrute Force Solution (Merge and Find Median)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Since both arrays are already sorted, we can use the two-pointer technique to merge them into a single sorted array. This is similar to the merge step in merge sort. We keep comparing the smallest elements from both arrays and add the smaller one to our result array.<\/li>\n\n\n\n
Once we have the merged array, finding the median is easy:\n\n
By merging, we get a single sorted array, and finding the median in a sorted array is straightforward.<\/p>\n\n\n\n
This approach is good for small arrays or when you want to build your understanding of the problem.<\/p>\n\n\n\nCode Implementation<\/h3>\n\n\n\n