Median of two sorted arrays Hard ​

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]

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];
    }
}

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.