ArrayProblem 35 of 36

Median of 2 sorted arrays of equal size

Brute Force
Time: O(n)
Space: O(n)
Optimal
Time: O(log n)
Space: O(1)

Problem Statement

Given two sorted arrays of equal size n, find the median of the merged array. The median is the middle element if the total number is odd, or the average of two middle elements if even.

Since both arrays have size n, the merged array has 2n elements (even), so median = (element at n-1 + element at n) / 2.

Example:

  • Input: arr1 = [1, 12, 15, 26, 38], arr2 = [2, 13, 17, 30, 45]
  • Output: 16
  • Explanation: Merged array: [1, 2, 12, 13, 15, 17, 26, 30, 38, 45]. Median = (15 + 17) / 2 = 16.

Approach 1: Brute Force (Merge Arrays)

Intuition

Merge both arrays and find the median directly from the merged array.

Algorithm

  1. Merge both sorted arrays
  2. Find the two middle elements
  3. Return their average
java
public class Solution {
    public double findMedian(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int[] merged = new int[2 * n];
        
        int i = 0, j = 0, k = 0;
        
        // Merge both arrays
        while (i < n && j < n) {
            if (arr1[i] <= arr2[j]) {
                merged[k++] = arr1[i++];
            } else {
                merged[k++] = arr2[j++];
            }
        }
        
        while (i < n) merged[k++] = arr1[i++];
        while (j < n) merged[k++] = arr2[j++];
        
        // Find median
        return (merged[n - 1] + merged[n]) / 2.0;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Merge operation takes linear time
  • Space Complexity: O(n) - Merged array storage

Approach 2: Count Without Merging

Intuition

We don't need to store all merged elements. Just count to the middle positions.

Algorithm

  1. Use two pointers to traverse both arrays
  2. Count elements until we reach positions n-1 and n
  3. Return average of these two elements
java
public class Solution {
    public double findMedian(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int i = 0, j = 0;
        int count = 0;
        int m1 = -1, m2 = -1;  // Two middle elements
        
        while (count <= n) {
            // m1 becomes previous m2
            m1 = m2;
            
            // Get next smallest element
            if (i == n) {
                m2 = arr2[j++];
            } else if (j == n) {
                m2 = arr1[i++];
            } else if (arr1[i] <= arr2[j]) {
                m2 = arr1[i++];
            } else {
                m2 = arr2[j++];
            }
            
            count++;
        }
        
        return (m1 + m2) / 2.0;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Traverse until middle
  • Space Complexity: O(1) - Only constant extra space

Approach 3: Optimal - Binary Search

Intuition

Use binary search to find the correct partition point. The median divides the merged array such that left half has n elements.

Algorithm

  1. Binary search on smaller array for partition point
  2. Partition divides both arrays such that all left elements ≤ all right elements
  3. Median is average of max(left) and min(right)
java
public class Solution {
    public double findMedian(int[] arr1, int[] arr2) {
        int n = arr1.length;
        
        // Ensure arr1 is smaller
        if (arr1.length > arr2.length) {
            return findMedian(arr2, arr1);
        }
        
        int low = 0, high = n;
        
        while (low <= high) {
            int cut1 = (low + high) / 2;
            int cut2 = n - cut1;
            
            // Elements on left and right of partition
            int left1 = (cut1 == 0) ? Integer.MIN_VALUE : arr1[cut1 - 1];
            int left2 = (cut2 == 0) ? Integer.MIN_VALUE : arr2[cut2 - 1];
            int right1 = (cut1 == n) ? Integer.MAX_VALUE : arr1[cut1];
            int right2 = (cut2 == n) ? Integer.MAX_VALUE : arr2[cut2];
            
            // Valid partition found
            if (left1 <= right2 && left2 <= right1) {
                return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
            }
            
            if (left1 > right2) {
                high = cut1 - 1;
            } else {
                low = cut1 + 1;
            }
        }
        
        return 0.0;  // Should never reach here
    }
}

Complexity Analysis

  • Time Complexity: O(log n) - Binary search on one array
  • Space Complexity: O(1) - Only constant extra space

Approach 4: Divide and Conquer

Intuition

Compare medians of both arrays. If they're equal, that's the answer. Otherwise, discard half of each array where median can't exist.

Algorithm

  1. Find medians m1 and m2 of both arrays
  2. If m1 == m2, return m1
  3. If m1 < m2, median is in [m1, end of arr1] and [start of arr2, m2]
  4. Recursively solve for reduced arrays
java
public class Solution {
    public double findMedian(int[] arr1, int[] arr2) {
        int n = arr1.length;
        return findMedianUtil(arr1, 0, n - 1, arr2, 0, n - 1);
    }
    
    private int median(int[] arr, int start, int end) {
        int n = end - start + 1;
        if (n % 2 == 0) {
            return (arr[start + n/2 - 1] + arr[start + n/2]) / 2;
        }
        return arr[start + n/2];
    }
    
    private int findMedianUtil(int[] arr1, int s1, int e1, 
                               int[] arr2, int s2, int e2) {
        int n = e1 - s1 + 1;
        
        // Base cases
        if (n == 1) {
            return (arr1[s1] + arr2[s2]) / 2;
        }
        
        if (n == 2) {
            return (Math.max(arr1[s1], arr2[s2]) + Math.min(arr1[e1], arr2[e2])) / 2;
        }
        
        int m1 = median(arr1, s1, e1);
        int m2 = median(arr2, s2, e2);
        
        if (m1 == m2) {
            return m1;
        }
        
        int halfLen = (n - 1) / 2;
        
        if (m1 < m2) {
            return findMedianUtil(arr1, s1 + halfLen, e1, arr2, s2, e2 - halfLen);
        } else {
            return findMedianUtil(arr1, s1, e1 - halfLen, arr2, s2 + halfLen, e2);
        }
    }
}

Complexity Analysis

  • Time Complexity: O(log n) - Problem size halves each iteration
  • Space Complexity: O(log n) - Recursion stack

Key Takeaways

  1. Equal size simplifies - We know exactly n elements on each side
  2. Binary search on partition - Find correct cut point in O(log n)
  3. Divide and conquer - Compare medians and discard half
  4. Edge cases - Handle INT_MIN/INT_MAX for boundary partitions
  5. Foundation for different sizes - Same technique extends to unequal arrays
Previous
Minimum no. of operations required to make an array palindrome
Next
Median of 2 sorted arrays of different size