Scale Engineer

Median of Two Sorted Arrays

Hard
#0004Time: O(m + n)Space: O(m + n)42 companies
Algorithms
Binary SearchDivide and Conquer
Data structures
Array
Companies
AccentureAdobeAkamaiAmazon

Prompt

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
  • -106 <= nums1[i], nums2[i] <= 106

Approaches

3 approaches with complexity analysis and trade-offs.

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

Walkthrough

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

Time

O(m + n)

Space

O(m + n)

Trade-offs

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem