Median of Two Sorted Arrays

HARD

Description

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

Example 1:

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

Example 2:

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.

Constraints:

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

Approaches

Checkout 3 different approaches to solve Median of Two Sorted Arrays. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Merge and Find Median

This approach involves merging the two sorted arrays into a single sorted array. Once the merged array is created, the median can be easily found based on the total number of elements.

Algorithm

1. Create a new array merged of size m + n.
1. Initialize three pointers: i for nums1, j for nums2, and k for merged, all starting at 0.
1. While i < m and j < n, compare nums1[i] and nums2[j]. Add the smaller element to merged[k] and increment the corresponding pointers.
1. If any elements remain in nums1, copy them to merged.
1. If any elements remain in nums2, copy them to merged.
1. Calculate the total length total = m + n.
1. If total is odd, return merged[total / 2].
1. If total is even, return the average of merged[total / 2 - 1] and merged[total / 2].

The most straightforward way to solve this problem is to combine the two sorted arrays, nums1 and nums2, into a single, larger sorted array called merged.

We can use a standard merge algorithm, similar to the one used in Merge Sort. We initialize two pointers, one for each input array, and iteratively pick the smaller of the two elements pointed to, adding it to our merged array and advancing the corresponding pointer.

After one of the arrays is fully traversed, we append the remaining elements of the other array to merged.

Once the merged array of size m + n is complete, finding the median is simple:

If the total length m + n is odd, the median is the element at the middle index, merged[(m + n) / 2].
If the total length is even, the median is the average of the two middle elements, (merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0.

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 total = m + n;
        if (total % 2 == 1) {
            return (double) merged[total / 2];
        } else {
            int mid1 = merged[total / 2 - 1];
            int mid2 = merged[total / 2];
            return (double) (mid1 + mid2) / 2.0;
        }
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Conceptually simple and easy to implement.
Leverages the basic merge operation, which is a fundamental algorithm.

Cons:

Inefficient in terms of space, as it requires an auxiliary array of size m + n.
Time complexity does not meet the problem's requirement of O(log(m+n)).

Code Solutions

Checking out 5 solutions in different languages for Median of Two Sorted Arrays. Click on different languages to view the code.

public class Solution {
    private int m;
    private int n;
    private int[] nums1;
    private int[] nums2;
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        m = nums1.Length;
        n = nums2.Length;
        this.nums1 = nums1;
        this.nums2 = nums2;
        int a = f(0, 0, (m + n + 1) / 2);
        int b = f(0, 0, (m + n + 2) / 2);
        return (a + b) / 2.0;
    }
    private int f(int i, int j, int k) {
        if (i >= m) {
            return nums2[j + k - 1];
        }
        if (j >= n) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.Min(nums1[i], nums2[j]);
        }
        int p = k / 2;
        int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;
        int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;
        return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);
    }
}

Video Solution

Watch the video walkthrough for Median of Two Sorted Arrays

Algorithms:

Binary SearchDivide and Conquer

Data Structures:

Array

Companies:

Accenture |Adobe |Akamai |Amazon |