# LeetCode 4. Median of Two Sorted Arrays

## Description

https://leetcode.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

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

The median is 2.0
```

Example 2:

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

The median is (2 + 3)/2 = 2.5
```

## Explanation

This is a classical coding interview question. Hard and worth thinking.

We can convert the problem to the problem of finding kth element after merging Array A and B, where k is (Array A’s length + Array B’ Length) / 2.

• If any of the two arrays is empty, then the kth element is the non-empty array’s kth element.
• If k == 1, the kth element is the first element of A or B.
• For all other cases, we compare the (k / 2) th number in A and the (k / 2) th number in B. If the array has no more than k /2 elements, we set key = MAX_VALUE. If keyA < keyB, we get rid of first k /2 elements. We keep searching in the remainder for the (k – k /2) th element.

## Java Solution

```public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 1) {
return findKth(nums1, 0, nums2, 0, len / 2 + 1);
} else {
return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
}
}

public int findKth(int[] A, int startA, int[] B, int startB, int k) {
if (startA >= A.length) {
return B[startB + k - 1];
}

if (startB >= B.length) {
return A[startA + k - 1];
}

if (k == 1) {
return Math.min(A[startA], B[startB]);
}

int indexA = startA + k / 2 - 1;
int indexB = startB + k / 2 - 1;
int keyA = indexA < A.length ? A[indexA] : Integer.MAX_VALUE;
int keyB = indexB < B.length ? B[indexB] : Integer.MAX_VALUE;

if (keyA < keyB) {
return findKth(A, startA + k / 2, B, startB, k - k / 2);
} else {
return findKth(A, startA, B, startB + k / 2, k - k / 2);
}
}
}
```

## 2 Thoughts to “LeetCode 4. Median of Two Sorted Arrays”

1. Stephen Boesch says:

It looks like the solution makes up to k/2 recursive calls. That is quite costly in stack manipulation. It would be better to do a mergesort type approach on k/2 elements.

2. Carlos Blanco says:

This problem is really hard.