Course4all
Join us on telegram
Home/dsa/Two Pointers/Median of Two Sorted Arrays

Median of Two Sorted Arrays

Master this topic with zero to advance depth.

Median of Two Sorted Arrays

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)).

Visual Representation

nums1: [1, 3], nums2: [2] Merged Sorted View: [ 1, 2, 3 ] ^ Median = 2.0 Partition View (Optimal): nums1: [ 1 | 3 ] nums2: [ 2 | ] Left Side: {1, 2}, Right Side: {3} Median = Max(Left) = 2.0
Hard

Examples

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

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

Approach 1

Level I: Brute Force (Merge Sort Style)

Intuition

Merge the two sorted arrays into a single sorted array and find the middle element(s).

Use the merge step from Merge Sort to combine the two arrays into one of size m+n. Calculate the median from the result.

⏱ O(M+N)💾 O(M+N)

Detailed Dry Run

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

  1. Combined array length = 3.
  2. Merge: i=0, j=0. nums1[0] < nums2[0] (1 < 2), merged = [1], i=1.
  3. i=1, j=0. nums2[0] < nums1[1] (2 < 3), merged = [1, 2], j=1.
  4. i=1, j=1. nums1[1] = 3, merged = [1, 2, 3], i=2.
  5. Median = merged[3/2] = merged[1] = 2.0.
java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[] merged = new int[m + n];
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
    while (i < m) merged[k++] = nums1[i++];
    while (j < n) merged[k++] = nums2[j++];
    if ((m + n) % 2 == 0) return (merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0;
    return merged[(m + n) / 2];
}

⚠️ Common Pitfalls & Tips

Violates the O(log(M+N)) time requirement. Uses O(M+N) space.

Approach 2

Level II: Better (Two Pointers - Merge Part Only)

Intuition

Since both arrays are already sorted, we can use the merge step of Merge Sort to combine them in O(M+N). We don't even need to store the whole combined array; we only need to keep track of the middle elements.

Iterate through both arrays using two pointers, keeping track of the values seen. Stop when we reach the middle index (or indices if even).

⏱ O(M+N)💾 O(1)

Detailed Dry Run

Input: [1, 3], [2]

  1. Total size 3, Median index 1.
  2. Pointers: i=0, j=0. Compare 1 and 2. 1 is smaller. count=0, val=1, i=1.
  3. Compare 3 and 2. 2 is smaller. count=1, val=2, j=1.
  4. Median is 2.
java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n1 = nums1.length, n2 = nums2.length, n = n1 + n2;
    int i=0, j=0, count=0, m1=-1, m2=-1;
    while (count <= n/2) {
        m2 = m1;
        if (i < n1 && (j >= n2 || nums1[i] < nums2[j])) m1 = nums1[i++];
        else m1 = nums2[j++];
        count++;
    }
    if (n % 2 == 0) return (m1 + m2) / 2.0;
    return m1;
}

⚠️ Common Pitfalls & Tips

O(M+N) is good but the problem asks for O(log(M+N)).

Approach 3

Level III: Optimal (Binary Search on Partitions)

Intuition

Instead of merging, we can partition the two arrays into two halves (left and right) such that the left half contains half of the elements and all elements in the left half are <= all elements in the right half.

Binary search on the smaller array to find a partition. For array A (smaller) at midA, and array B at midB = (total+1)/2 - midA, checking if A[midA-1] <= B[midB] and B[midB-1] <= A[midA].

⏱ O(log(min(M,N)))💾 O(1)

Detailed Dry Run

Input: nums1 = [1,3], nums2 = [2] Total elements = 3. Target partition size for left half = (3+1)/2 = 2.

  1. Assume nums1 is the smaller array (x=2, y=1).

  2. Binary search partitionX in nums1 from low=0 to high=2.

    • Try partitionX = 1 (mid of 0,2).

      • partitionY = (2+1+1)/2 - 1 = 2 - 1 = 1.
      • maxLeftX = nums1[0] = 1
      • minRightX = nums1[1] = 3
      • maxLeftY = nums2[0] = 2
      • minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY] -> nums2[1] is out of bounds, so minRightY = Infinity.

    • Check conditions: maxLeftX <= minRightY (1 <= Infinity) -> True. maxLeftY <= minRightX (2 <= 3) -> True.

    • Conditions met! Total elements (3) is odd. Median = max(maxLeftX, maxLeftY) = max(1, 2) = 2.0.

java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    int x = nums1.length, y = nums2.length;
    int low = 0, high = x;
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;
        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) return (double)(Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            else return (double)Math.max(maxLeftX, maxLeftY);
        } else if (maxLeftX > minRightY) high = partitionX - 1;
        else low = partitionX + 1;
    }
    return 0.0;
}

⚠️ Common Pitfalls & Tips

Be careful with the partition logic and even/odd total counts. Binary search must be on the smaller array for O(log(min(M,N))).

← Previous QuestionTrapping Rain Water
Next Question →Shortest Palindrome