Skip to content
AI360Xpert
Back to Binary Search
Hard

Median of Two Sorted Arrays

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

Examples

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

Constraints

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

Approach

Merge the two sorted arrays into a single sorted array. Then, find the median of the merged array. If the length is odd, the median is the middle element. If the length is even, the median is the average of the two middle elements.

Complexity Analysis

Time Complexity
O(m + n)
Space Complexity
O(m + n)

This is the most intuitive approach but does not meet the O(log(m+n)) time complexity requirement.

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