Median Of Two Sorted Arrays Solution for Microsoft

Company: Microsoft · Difficulty: Easy · Topics: Array, Binary Search, Divide and Conquer

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Examples

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.00000

Explanation: merged array = [0,0,0,0] and median is (0 + 0) / 2 = 0.

Example 4:

Input: nums1 = [], nums2 = [1]

Output: 1.00000

Explanation: merged array = [1] and median is 1.

Example 5:

Input: nums1 = [2], nums2 = []

Output: 2.00000

Explanation: merged array = [2] and median is 2.

Intuition

The key insight is that we don't need to merge the arrays. Instead, we can use binary search to find the correct partition that divides both arrays into left and right halves such that all elements in the left half are less than all elements in the right half. The median will be the average of the maximum element from the left partition and the minimum element from the right partition.

Approach

Approach 1: Binary Search (Optimal)

1. Ensure nums1 is the smaller array for efficiency

2. Use binary search on the smaller array to find the correct partition

3. Calculate corresponding partition in the larger array

4. Check if the partition is correct (all left elements ≤ all right elements)

5. Calculate median based on partition

Approach 2: Merge and Find

1. Merge the two sorted arrays

2. Find the median of the merged array

3. Time complexity: O(m+n), Space: O(m+n)

Approach 3: Two Pointers

1. Use two pointers to traverse both arrays

2. Count elements until we reach the median position

3. Time complexity: O((m+n)/2)

Dry Run

Let's trace through Example 1: nums1 = [1,3], nums2 = [2]

Binary Search Approach:

• Ensure nums1 is smaller: nums1=[1,3], nums2=[2]
• Binary search on nums1: low=0, high=2
• mid=1: partition1=1, partition2=0
• Check: maxLeft1=1, minRight1=3, maxLeft2=-∞, minRight2=2
• Condition: maxLeft1(1) ≤ minRight2(2) ✓, maxLeft2(-∞) ≤ minRight1(3) ✓
• Median = max(maxLeft1, maxLeft2) = max(1, -∞) = 1

Merge Approach:

• Merged array: [1,2,3]
• Median = 2 (middle element)

Solution

Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.

Key Insights:

1. Binary Search: The key insight is that we don't need to merge arrays - we just need to find the correct partition point

2. Partition Logic: A correct partition ensures all elements in left half ≤ all elements in right half

3. Edge Cases: Handle empty arrays and arrays of different sizes properly

Edge Cases:

• One array is empty: return median of the other array
• Both arrays have same size: partition logic becomes simpler
• Arrays have very different sizes: ensure we search on the smaller array

Time Complexity

• Best Case: O(log(min(m,n))) - Binary search on smaller array
• Average Case: O(log(min(m,n))) - Binary search approach
• Worst Case: O(m+n) - Merge approach

Space Complexity

• Best Case: O(1) - Binary search approach
• Average Case: O(1) - In-place operations
• Worst Case: O(m+n) - Merge approach

More Microsoft coding questions