Median Of Two Sorted Arrays Solution for Accenture

Company: Accenture · Difficulty: Hard · 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.

Key Understanding:

Both arrays are already sorted in ascending order
We need to find the median of the combined sorted array
For odd total length: return the middle element
For even total length: return average of two middle elements
Time complexity must be O(log(m+n))

Examples

Example 1:

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

Output: 2.00000

Explanation:

Combined sorted array: [1,2,3]
Total length = 3 (odd)
Median = middle element = 2
Visual: [1,2,3] → median = 2

Example 2:

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

Output: 2.50000

Explanation:

Combined sorted array: [1,2,3,4]
Total length = 4 (even)
Median = average of middle elements = (2+3)/2 = 2.5
Visual: [1,2,3,4] → median = (2+3)/2 = 2.5

Example 3:

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

Output: 0.00000

Explanation:

Combined sorted array: [0,0,0,0]
Total length = 4 (even)
Median = average of middle elements = (0+0)/2 = 0

Example 4:

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

Output: 1.00000

Explanation:

Combined sorted array: [1]
Total length = 1 (odd)
Median = middle element = 1

Intuition

The key insight is that we don't need to actually merge the arrays. Instead, we can use binary search to find the correct partition point that divides both arrays into left and right halves.

Binary Search Approach:

1. Partition Concept: We need to find a partition that divides all elements into left and right halves

2. Left Half: Contains smaller elements from both arrays

3. Right Half: Contains larger elements from both arrays

4. Median: The largest element from left half and smallest from right half

Why Binary Search Works:

We can binary search on the smaller array to find the correct partition
At each step, we can determine if we need to move left or right
The partition must satisfy: maxLeftX ≤ minRightY AND maxLeftY ≤ minRightX

Approach

Approach 1: Binary Search (Optimal)

Algorithm:

1. Ensure nums1 is the smaller array (swap if needed)

2. Binary search on nums1 to find the correct partition

3. For each partition, calculate corresponding partition in nums2

4. Check if the partition is correct (maxLeft ≤ minRight)

5. Return median based on total length (odd/even)

Key Steps:

Calculate partitionX = (low + high) / 2
Calculate partitionY = (m + n + 1) / 2 - partitionX
Check if partition is valid
Adjust search range based on comparison

Approach 2: Merge and Find (Linear)

Algorithm:

1. Merge the two sorted arrays

2. Find median based on total length

3. Return the median value

Limitations:

Time complexity: O(m+n)
Space complexity: O(m+n)
Does not meet the O(log(m+n)) requirement

Approach 3: Two Pointers (Linear)

Algorithm:

1. Use two pointers to traverse both arrays

2. Count elements until reaching median position

3. Return median value

Limitations:

Time complexity: O(m+n)
Space complexity: O(1)
Does not meet the O(log(m+n)) requirement

Dry Run

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

Step 1: Ensure nums1 is smaller

nums1 length = 2, nums2 length = 1
nums1 is larger, so swap: nums1 = [2], nums2 = [1,3]

Step 2: Binary search on nums1

low = 0, high = 1
partitionX = 0
partitionY = (1 + 2 + 1) / 2 - 0 = 2

Step 3: Check partition

maxLeftX = -∞ (no elements)
minRightX = 2
maxLeftY = 3 (element at index 1)
minRightY = ∞ (no elements)

Step 4: Check validity

maxLeftX ≤ minRightY: -∞ ≤ ∞ ✓
maxLeftY ≤ minRightX: 3 ≤ 2 ✗

Step 5: Adjust search

Move right: low = 1
partitionX = 1
partitionY = 1

Step 6: Final partition

maxLeftX = 2
minRightX = ∞
maxLeftY = 1
minRightY = 3

Step 7: Check validity

maxLeftX ≤ minRightY: 2 ≤ 3 ✓
maxLeftY ≤ minRightX: 1 ≤ ∞ ✓

Step 8: Calculate median

Total length = 3 (odd)
Median = max(maxLeftX, maxLeftY) = max(2, 1) = 2

Key Insights

1. Partition Strategy: The key is finding the correct partition that divides all elements into two equal halves

2. Binary Search Efficiency: We only need to search on the smaller array, making it O(log(min(m,n)))

3. Boundary Conditions: Handle edge cases like empty arrays, single elements, and all equal elements

4. Median Calculation: Different for odd vs even total lengths

5. Partition Validation: Must ensure all elements in left half are ≤ all elements in right half

Edge Cases

1. Empty Arrays: Handle when one or both arrays are empty

2. Single Elements: Arrays with only one element each

3. All Equal Elements: Arrays with all same values

4. Different Sizes: Arrays with significantly different sizes

5. No Overlap: Arrays with completely different value ranges

6. Large Arrays: Handle arrays with millions of elements efficiently

Time & Space Complexity

Approach 1 (Binary Search):

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

Approach 2 (Merge):

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

Approach 3 (Two Pointers):

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