Median of Two Sorted Arrays Problem and Solution

1. Introduction

The "Median of Two Sorted Arrays" problem involves finding the median of two sorted arrays. The goal is to merge the two sorted arrays and find the median of the combined array. This problem is interesting because it challenges you to find an efficient solution, as simply merging and then finding the median would be too inefficient for large arrays.

2. Solution in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    nums1.insert(nums1.end(), nums2.begin(), nums2.end());
    sort(nums1.begin(), nums1.end());
    int n = nums1.size();
    return n % 2 == 0 ? (nums1[n/2 - 1] + nums1[n/2]) / 2.0 : nums1[n/2];
}

// Example usage
int main() {
    vector<int> nums1 = {1, 3};
    vector<int> nums2 = {2};
    cout << "Median: " << findMedianSortedArrays(nums1, nums2) << endl;
    return 0;
}

Output:

Median: 2

Explanation:

1. The function findMedianSortedArrays takes two sorted vectors nums1 and nums2.

2. It merges nums2 into nums1.

3. The merged vector is then sorted.

4. The median is calculated based on the size of the merged vector: if the size is even, the median is the average of the two middle elements; if odd, it's the middle element.

3. Solution in Java

import java.util.Arrays;

public class MedianOfArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, merged, 0, nums1.length);
        System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
        Arrays.sort(merged);
        int n = merged.length;
        return n % 2 == 0 ? (merged[n/2 - 1] + merged[n/2]) / 2.0 : merged[n/2];
    }

    // Example usage
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: " + findMedianSortedArrays(nums1, nums2));
    }
}

Output:

Median: 2.0

Explanation:

1. The method findMedianSortedArrays takes two sorted arrays nums1 and nums2.

2. The arrays are merged into a new array merged.

3. The merged array is sorted.

4. The median is calculated in the same way as the C++ solution, considering the even and odd lengths of the merged array.

4. Solution in Python

def find_median_sorted_arrays(nums1, nums2):
    nums = sorted(nums1 + nums2)
    n = len(nums)
    return (nums[n // 2] + nums[(n - 1) // 2]) / 2.0

# Example usage
nums1 = [1, 3]
nums2 = [2]
print("Median:", find_median_sorted_arrays(nums1, nums2))

Output:

Median: 2.0

Explanation:

1. The function find_median_sorted_arrays merges the two lists nums1 and nums2 and sorts the combined list.

2. The median is calculated by averaging the middle element(s), similar to the C++ and Java solutions.

3. The solution handles both the even and odd lengths of the merged list.