Appearance

# Median of two sorted arrays Hard

## Question

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

.

txt

```
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
```

txt

```
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
```

```
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
```

## Solution

python

```
def findMedianSortedArrays(nums1, nums2):
merged = sorted(nums1 + nums2)
n = len(merged)
if n % 2 == 0:
mid = n // 2
return (merged[mid - 1] + merged[mid]) / 2
else:
return merged[n // 2]
```

java

```
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] merged = new int[nums1.length + nums2.length];
int i = 0, j = 0, k = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
merged[k++] = nums1[i++];
} else {
merged[k++] = nums2[j++];
}
}
while (i < nums1.length) {
merged[k++] = nums1[i++];
}
while (j < nums2.length) {
merged[k++] = nums2[j++];
}
int n = merged.length;
if (n % 2 == 0) {
int mid = n / 2;
return (merged[mid - 1] + merged[mid]) / 2.0;
} else {
return merged[n / 2];
}
}
```

javascript

```
function findMedianSortedArrays(nums1, nums2) {
const merged = [...nums1, ...nums2].sort((a, b) => a - b);
const n = merged.length;
if (n % 2 === 0) {
const mid = n / 2;
return (merged[mid - 1] + merged[mid]) / 2;
} else {
return merged[Math.floor(n / 2)];
}
}
```

## Notes

You are given two sorted arrays, `nums1`

and `nums2`

, of sizes `m`

and `n`

respectively. You need to find the median of the combined sorted array formed by merging both `nums1`

and `nums2`

.

The median of a sorted array is the middle element if the array has an odd number of elements. If the array has an even number of elements, the median is the average of the middle two elements.

### Time and Space Complexity Analysis:

The time complexity of the given solutions primarily depends on the sorting operation, which takes `O((m + n) \* log(m + n))`

time. The space complexity for all solutions is O(m + n) because of the merged array.

The problem statement specifically mentions that the overall run time complexity should be O(log(m + n)). Achieving O(log(m + n)) time complexity involves using a more advanced algorithm called the Median of Two Sorted Arrays algorithm, which is beyond the scope of this simple merging approach.

To summarize:

- Time Complexity:
`O((m + n) \* log(m + n))`

- Space Complexity:
`O(m + n)`

Keep in mind that this solution, while straightforward, does not achieve the desired O(log(m + n)) time complexity as requested in the problem statement. Achieving that optimal time complexity requires more advanced algorithms like binary search.