LeetCode 4. Median of Two Sorted Arrays

Description

https://leetcode.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Explanation

This is a classical coding interview question. Hard and worth thinking.

We can convert the problem to the problem of finding kth element after merging Array A and B, where k is (Array A’s length + Array B’ Length) / 2.

• If any of the two arrays is empty, then the kth element is the non-empty array’s kth element.
• If k == 1, the kth element is the first element of A or B.
• For all other cases, we compare the (k / 2) th number in A and the (k / 2) th number in B. If the array has no more than k /2 elements, we set key = MAX_VALUE. If keyA < keyB, we get rid of first k /2 elements. We keep searching in the remainder for the (k – k /2) th element.

Video Tutorial

Java Solution

public class Solution { 
    public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
        int len = nums1.length + nums2.length; 
        if (len % 2 == 1) { 
            return findKth(nums1, 0, nums2, 0, len / 2 + 1); 
        } else { 
            return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0; 
        } 
    } 
     
    public int findKth(int[] A, int startA, int[] B, int startB, int k) { 
        if (startA >= A.length) { 
            return B[startB + k - 1]; 
        } 
         
        if (startB >= B.length) { 
            return A[startA + k - 1]; 
        } 
         
        if (k == 1) { 
            return Math.min(A[startA], B[startB]); 
        } 
         
        int indexA = startA + k / 2 - 1; 
        int indexB = startB + k / 2 - 1; 
        int keyA = indexA < A.length ? A[indexA] : Integer.MAX_VALUE; 
        int keyB = indexB < B.length ? B[indexB] : Integer.MAX_VALUE; 
         
        if (keyA < keyB) { 
            return findKth(A, startA + k / 2, B, startB, k - k / 2); 
        } else { 
            return findKth(A, startA, B, startB + k / 2, k - k / 2); 
        } 
    } 
}