Median of 2 Sorted Lists
Problem Statement
Given two sorted arrays arr1[] and arr2[], find the median of the two sorted arrays. The overall run time complexity should be O(log(min(m,n))).
Example 1: Input: arr1 = [1, 3], arr2 = [2]
Output: 2.0
Explanation: Merged array = [1, 2, 3], median is 2.
Example 2: Input: arr1 = [1, 2], arr2 = [3, 4]
Output: 2.5
Explanation: Merged array = [1, 2, 3, 4], median is (2 + 3)/2 = 2.5
Approach 1: Merge and Find Median
Explanation: Merge both sorted arrays into a single sorted array using the merge procedure of merge sort, then find the median from the merged array.
Time Complexity: O(m + n)
Space Complexity: O(m + n)
function findMedian(arr1, arr2):
m = length(arr1)
n = length(arr2)
merged = new array of size m + n
i = 0, j = 0, k = 0
while i < m and j < n:
if arr1[i] < arr2[j]:
merged[k] = arr1[i]
i = i + 1
else:
merged[k] = arr2[j]
j = j + 1
k = k + 1
while i < m:
merged[k] = arr1[i]
i = i + 1
k = k + 1
while j < n:
merged[k] = arr2[j]
j = j + 1
k = k + 1
total = m + n
if total % 2 == 1:
return merged[total / 2]
else:
return (merged[total / 2 - 1] + merged[total / 2]) / 2.0
💡 Think: Merge both arrays and read the middle position(s).
Approach 2: Without Extra Space (Counting)
Explanation: Instead of creating a merged array, use two pointers to traverse both arrays and count elements until reaching the median position(s). Only store the median element(s).
Time Complexity: O(m + n)
Space Complexity: O(1)
function findMedian(arr1, arr2):
m = length(arr1)
n = length(arr2)
total = m + n
i = 0, j = 0, count = 0
median1 = 0, median2 = 0
medianPos1 = total / 2
medianPos2 = total / 2 - 1
while count <= medianPos1:
if i < m and j < n:
if arr1[i] < arr2[j]:
median2 = median1
median1 = arr1[i]
i = i + 1
else:
median2 = median1
median1 = arr2[j]
j = j + 1
else if i < m:
median2 = median1
median1 = arr1[i]
i = i + 1
else:
median2 = median1
median1 = arr2[j]
j = j + 1
count = count + 1
if total % 2 == 1:
return median1
else:
return (median1 + median2) / 2.0
💡 Think: Walk both arrays without storing all, stop when you hit median index.
Approach 3: Binary Search (Divide and Conquer)
Explanation: Use binary search on the smaller array to find the correct partition. The partition divides both arrays such that all elements on the left are smaller than elements on the right. This ensures the median is at the partition boundary.
Time Complexity: O(log(min(m,n)))
Space Complexity: O(1)
function findMedian(arr1, arr2):
if length(arr1) > length(arr2):
swap(arr1, arr2)
m = length(arr1)
n = length(arr2)
low = 0, high = m
while low <= high:
partition1 = (low + high) / 2
partition2 = (m + n + 1) / 2 - partition1
maxLeft1 = (partition1 == 0) ? -infinity : arr1[partition1 - 1]
minRight1 = (partition1 == m) ? infinity : arr1[partition1]
maxLeft2 = (partition2 == 0) ? -infinity : arr2[partition2 - 1]
minRight2 = (partition2 == n) ? infinity : arr2[partition2]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
if (m + n) % 2 == 0:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
else:
return max(maxLeft1, maxLeft2)
else if maxLeft1 > minRight2:
high = partition1 - 1
else:
low = partition1 + 1
💡 Think: Aim for equal split of the combined length; move the partition left if maxLeft1 > minRight2, otherwise move it right, and compute the median from the partition edges.
