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
    
    // Merge both arrays
    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
    
    // Find median
    total = m + n
    if total % 2 == 1:
        return merged[total / 2]
    else:
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0

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
    
    // Find median position(s)
    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

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):
    // Ensure arr1 is the smaller array
    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
        
        // Find boundary elements
        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]
        
        // Check if we found the correct partition
        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            // Found correct partition
            if (m + n) % 2 == 0:
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
            else:
                return max(maxLeft1, maxLeft2)
        else if maxLeft1 > minRight2:
            // Move towards left in arr1
            high = partition1 - 1
        else:
            // Move towards right in arr1
            low = partition1 + 1

The Binary Search approach (Divide and Conquer) is the optimal solution with O(log(min(m,n))) time complexity. It efficiently finds the median without merging the arrays by using binary search to partition both arrays correctly.


Flowchart