Median of Two Sorted Arrays — Leetcode

Topic: Array
Difficulty: Hard
Question Number: 4

Problem statement:
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.

Explanation:

There are two approaches to solve this question.

Approach 1:

• Find the length of the two arrays m and n respectively.
• Add the sum, check whether the following sum is even or odd, and use the formula accordingly.

If even — m+n/2
If odd — m+n+1/2

Approach 2:

We will be solving the question by using a binary search method.

• Initialze two pointers —

Start = 0
End = m

• Loop until Start meets End i.e.,

(Start≤End)

• Calculate the partition index of num1 array which will be the mid-point of start and end i.e.,

(Start+End)/2

• Calculate the partition index of num2 array.

(m+n+1)/2 - partition index of num1 array

• Now, we can have three cases -

(i) If (MaxNum1 <= MinNum2 && MaxNum2 <= MinNum1)
we can return the median (M+N)

(ii) Else If (MaxNum1 > MinNum2)
it means, we are too far on the right and we need to go on the left, so

End = partition index of num1 array-1

(iii) Else, we are too far on the left and we need to go to the right, so

Start = partition index of num1 array + 1

We didn’t find the median so again iterate over from above and find new min and max values for the same!

Code:
(in java)

//Approach one

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int n = n1 + n2;
        int[] new_arr = new int[n];

        int i=0, j=0, k=0;

        while (i<=n1 && j<=n2) {
            if (i == n1) {
                while(j<n2) new_arr[k++] = nums2[j++];
                break;
            } else if (j == n2) {
                while (i<n1) new_arr[k++] = nums1[i++];
                break;
            }

            if (nums1[i] < nums2[j]) {
                new_arr[k++] = nums1[i++];
            } else {
                new_arr[k++] = nums2[j++];
            }
        }

        if (n%2==0) return (float)(new_arr[n/2-1] + new_arr[n/2])/2;
        else return new_arr[n/2];
    }
}

//Approach two

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int start = 0;
        int end = m;
        while (start <= end) {
            int partitionNums1 = (start + end) / 2;
            int partitionNums2 = (m + n + 1) / 2 - partitionNums1;
            int maxLeftNums1 = partitionNums1 == 0 ? Integer.MIN_VALUE : nums1[partitionNums1 - 1];
            int minRightNums1 = partitionNums1 == m ? Integer.MAX_VALUE : nums1[partitionNums1];
            int maxLeftNums2 = partitionNums2 == 0 ? Integer.MIN_VALUE : nums2[partitionNums2 - 1];
            int minRightNums2 = partitionNums2 == n ? Integer.MAX_VALUE : nums2[partitionNums2];
            if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeftNums1, maxLeftNums2) + Math.min(minRightNums1, minRightNums2)) / 2.0;
                } else {
                    return Math.max(maxLeftNums1, maxLeftNums2);
                }
            }
            else if (maxLeftNums1 > minRightNums2) {
                end = partitionNums1 - 1;
            }
            else {
                start = partitionNums1 + 1;
            }
        }
        throw new IllegalArgumentException();
    }
}

Thank You
Oshi Raghav