Median of the two sorted arrays.

Problem Statement

Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays.

The overall run time complexity should be:

O(log(min(N,M)))

---

Brute Force Intuition

In an interview, you can explain it like this:

Since both arrays are sorted, we can merge them into a single sorted array and then directly compute the median from the merged array.

Complexity

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Brute Force Code

int[] merged = new int[n + m];

// Merge both arrays

return median;

---

Moving Towards the Optimal Approach

Do we really need the merged array?

No.

We only care about:

Left Half
Right Half

such that:

All elements in Left Half
<=
All elements in Right Half

This is where partition-based Binary Search comes in.

---

Pattern Recognition

Whenever you see:

• Two Sorted Arrays
• Median
• O(log N) expected

Think:

Binary Search on Partition

---

Key Observation

For total elements:

n + m

Left partition should contain:

(n + m + 1) / 2

elements.

We Binary Search on:

How many elements to take from nums1

Remaining automatically come from nums2.

---

Optimal Java Solution

class Solution {

    public double findMedianSortedArrays(int[] nums1,
                                         int[] nums2) {

        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);

        int n1 = nums1.length;
        int n2 = nums2.length;

        int low = 0;
        int high = n1;

        while (low <= high) {

            int cut1 = low + (high - low) / 2;

            int cut2 =
                (n1 + n2 + 1) / 2 - cut1;

            int left1 =
                cut1 == 0 ? Integer.MIN_VALUE
                           : nums1[cut1 - 1];

            int left2 =
                cut2 == 0 ? Integer.MIN_VALUE
                           : nums2[cut2 - 1];

            int right1 =
                cut1 == n1 ? Integer.MAX_VALUE
                            : nums1[cut1];

            int right2 =
                cut2 == n2 ? Integer.MAX_VALUE
                            : nums2[cut2];

            if (left1 <= right2 &&
                left2 <= right1) {

                if ((n1 + n2) % 2 == 0) {

                    return (Math.max(left1, left2)
                          + Math.min(right1, right2))
                          / 2.0;
                }

                return Math.max(left1, left2);
            }

            else if (left1 > right2) {

                high = cut1 - 1;

            } else {

                low = cut1 + 1;
            }
        }

        return 0;
    }
}

---

Dry Run

Input

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

Total:

3 elements

Need:

2 elements on left side

Partition:

[1] | [3]

[2] |

Check:

left1 <= right2
left2 <= right1

Valid Partition.

Median:

max(1,2)
=
2

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(log(min(N,M)))
Space Complexity	O(1)

---

Interview One-Liner

Binary search the partition of the smaller array and ensure all elements on the left side are less than or equal to all elements on the right side.

---

Pattern Learned

Two Sorted Arrays
+
Median
+
Logarithmic Requirement

=> Binary Search on Partition