GeetCode Hub

  1. Home
  2. GeetCode
  3. GeetCode Hub

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.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

 

Constraints:

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

public double findMedianSortedArrays(int[] nums1, int[] nums2) { int x = nums1.length; int y = nums2.length; if(x > y){ return findMedianSortedArrays(nums2, nums1); } int low = 0; int high = x; double median = 0.0; while(low<=high){ int partitionX = (low + high)/2; int partitionY = (x+y+1)/2 - partitionX; int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX-1]; int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX]; int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY-1]; int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY]; if(maxLeftX <= minRightY && maxLeftY <= minRightX){ if((x+y)%2==0){ median = (Math.max(maxLeftX, maxLeftY) + Math.min(minRightY, minRightX))/2.0; } else{ median = Math.max(maxLeftX, maxLeftY); } break; } else if(maxLeftX > minRightY){ high = partitionX - 1; } else{ low = partitionX + 1; } } return median; }

The main gist of this solution is to use Binary search on the shorter size of Array and create partitioning in which both partitions will be having the same number of elements where all elements in the left partition is smaller than all the elements on the right side of the partition.

 

Time Complexity: O(log(min(m,n)) //Where m and n are the sizes of both the arrays.

Space Complexity: O(1) // We are not using any extra space.

Execution:

Input: