Leetcode 4: Median of Two Sorted Arrays

1. Problem Statement (Simple Explanation)

You are given two sorted arrays:

• nums1 of size m

• nums2 of size n

You need to return the median of the combined data if both arrays were merged into one sorted array.

Constraints:

• Total length m + n >= 1

• Arrays are individually sorted in non-decreasing order.

• You must achieve overall time complexity:

O(log(m+n))

The median:

• If total length is odd: middle element.

• If total length is even: average of the two middle elements.

2. Examples

Example 1

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

Output: 2.00000

Explanation: Merged array: [1, 2, 3] and Median = 2

Example 2

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: Merged array: [1, 2, 3, 4] and Median =2+32=2.5

3. Approach 1 – Merge and Find Median (Basic, O(m+n))

Intuition

Simulate the merging step of merge sort:

• Merge nums1 and nums2 into a single sorted array (or at least until we reach the median position).

• Compute the median from the merged data.

This is simple but runs in:

O(m+n)

which does not meet the required O(log(m+n)) constraint, but is a good starting explanation for beginners.

Algorithm (Step-by-Step)

1. Let m = len(nums1), n = len(nums2), total = m + n.

2. Use two pointers i = 0 (for nums1), j = 0 (for nums2).

3. Option A (fully merge):

• Create a new array merged, and push the smaller of nums1[i] and nums2[j] each step.

• After merging, if total is odd, return merged[total // 2]; else average merged[total // 2 - 1] and merged[total // 2].

4. Option B (partial merge, more space efficient):

• We only need elements up to the middle indices.

• Maintain two variables, prev and curr, updated each step until we reach the median position.

Pseudo-code (Partial Merge)

Complexity

• Time: O(m+n)

• Space: O(1) extra (with partial merge)

Good for understanding, but not optimal per problem requirement.

4. Approach 2 – Binary Search on Partition (Optimal, O(log(min(m, n))))

This is the standard interview solution.

Key Idea (Partition-Based)

We conceptually partition the combined sorted array into left and right halves such that:

• All elements on the left side are <= all elements on the right side.

• The left and right halves differ in size by at most 1.

We don’t actually merge, we just find such a partition by using binary search on one array.

We choose nums1 to be the shorter array (swap if needed).
We perform binary search on nums1's partition index i, and derive j for nums2.

Let:

• m = len(nums1), n = len(nums2) and assume m <= n.

• total = m + n.

• half = (total + 1) // 2 → number of elements that should be on the left side combined.

We choose some i from 0 to m, and then:

                                                        j=half-i

So:

• Left side = nums1[0..i-1] and nums2[0..j-1]

• Right side = nums1[i..m-1] and nums2[j..n-1]

We want the partition to be valid:

1. All elements on left ≤ all elements on right:

• nums1[i-1] <= nums2[j] (if i > 0 and j < n)

• nums2[j-1] <= nums1[i] (if j > 0 and i < m)

2. Once we have a valid partition:

• If total is odd: median is max(left parts)

• If total is even: median is average of max(left parts) and min(right parts)

We adjust i using binary search:

• If nums1[i-1] > nums2[j] → i is too big → move left.

• Else if nums2[j-1] > nums1[i] → i is too small → move right.

• Else → perfect partition.

To avoid index problems at borders, we treat out-of-bounds as ±∞, e.g.:

• If i == 0, then left1 = -∞ (no element)

• If i == m, then right1 = +∞

• Similarly for j.

Pseudo-code (Binary Search on Shorter Array)

Complexity

We binary-search only on the shorter array:

• Time: O(log(min(m,n)))

• Space: O(1)

Meets the required O(log(m+n)).

5. Java code

6. C code

7. C++ code

8. Python code

9. JavaScript

<<<PREV

NEXT>>>