Algorithm


Problem Name: 4. Median of Two Sorted Arrays

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

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

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


int bs(int *n, int sz, int k) {
    int i, j, m;
    i = 0;
    j = sz - 1;
    while (i  < = j) {
        m = i + (j - i) / 2;
        if (n[m] > k) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return j;   // this is the lastest one which is not greater than k
}
double bs2(int *n1, int sz1, int *n2, int sz2, int m, int m1) {
    double d;
    int i;
    i = bs(n1, sz1, n2[0]); // search in first array
    if (i >= m) {           // median is in the first array
        d = n1[m];
        if (m1) {
            if (i > m) {
                d += n1[m + 1];
            } else {
                d += n2[0];
            }
            d /= 2;
        }
    } else if (i == sz1 - 1) {  // median is in the second array
        d = n2[m - i - 1];
        if (m1) {
            d += n2[m - i];
            d /= 2;
        }
    } else {                    // reverse arrays and search again
        d = bs2(n2, sz2, &n1[i + 1], sz1 - i - 1, m - i - 1, m1);
    }
    return d;
}
int min(int a, int b) {
    return a  <  b ? a : b;
}
int max(int a, int b) {
    return a > b ? a : b;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    double d;
#if 0  // sliding & binary search
    int i1_left = 0, i1_right = nums1Size;
    int i1, i2;
    
    if (nums1Size > nums2Size) {  // make nums1 as a short array
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    }
    
    // O(log(min(m, n)))
    while (i1_left  < = i1_right) {
        i1 = i1_left + (i1_right - i1_left) / 2;
        i2 = (nums1Size + nums2Size + 1) / 2 - i1;
        if (i1 > 0 && nums1[i1 - 1] > nums2[i2]) {
            i1_right = i1 - 1;
        } else if (i1  <  nums1Size && nums1[i1] < nums2[i2 - 1]) {
            i1_left = i1 + 1;
        } else {
            // found it!
            if (i1 == 0) d = nums2[i2 - 1];
            else if (i2 == 0) d = nums1[i1 - 1];
            else if (nums1[i1 - 1] > nums2[i2 - 1]) d = nums1[i1 - 1];
            else d = nums2[i2 - 1];
            if (((nums1Size + nums2Size) % 2) == 0) {
                if (i2 == nums2Size) {
                    d = (d + nums1[i1]) / 2;
                } else if (i1 == nums1Size) {
                    d = (d + nums2[i2]) / 2;
                } else if (nums1[i1]  <  nums2[i2]) {
                    d = (d + nums1[i1]) / 2;
                } else {
                    d = (d + nums2[i2]) / 2;
                }
            }
            break;
        }
    }
#else // binary search 40+ms
    int p1, p2;
    
    p1 =  (nums1Size + nums2Size - 1) / 2;
    p2 = ((nums1Size + nums2Size) % 2) ? 0 : 1;
    
    if (nums2Size == 0) {
        d = nums1[p1];
        if (p2) {
            d += nums1[p1 + 1];
            d /= 2;
        }
        return d;
    }
    
    if (nums1Size == 0) {
        d = nums2[p1];
        if (p2) {
            d += nums2[p1 + 1];
            d /= 2;
        }
        return d;
    }

    if (nums2[0]  <  nums1[0]) return bs2(nums2, nums2Size, nums1, nums1Size, p1, p2);
    return bs2(nums1, nums1Size, nums2, nums2Size, p1, p2);
#endif
    
    return d;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums1 = [1,3], nums2 = [2]

Output

x
+
cmd
2.00000

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m > n) return findMedianSortedArrays(nums2, nums1);
        int lo = 0, hi = m, mid = (m + n + 1)/2;
        while(lo <= hi){
            int i = (lo + hi>/2;
            int j = mid - i;
            if(i  <  m && nums2[j - 1] > nums1[i]) 
                lo = i + 1;
            else if(i > 0  && nums1[i - 1] > nums2[j])
                hi = i - 1;
            else{
                int maxLeft = (i == 0) ? nums2[j - 1] : (j == 0) ? nums1[i - 1] : max(nums1[i - 1], nums2[j - 1]); 
                int minRight = (i == m) ? nums2[j] : (j == n) ? nums1[i] : min(nums1[i], nums2[j]);
                return (m + n) % 2 ? maxLeft : (maxLeft + minRight) / 2.0;
            }
        }
    }
};

Copy The Code & Try With Live Editor

Input

x
+
cmd
nums1 = [1,2], nums2 = [3,4]

Output

x
+
cmd
2.50000

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        ArrayList < Integer> arr = new ArrayList<>();
        
        int i = 0;
        int j = 0;
        int k = 0;
        int limit = (n)/2 + 1;
        
        while (i  <  nums1.length && j < nums2.length && k < limit) {
            if (nums1[i] < nums2[j]) {
                arr.add(nums1[i]);
                i++;
            }
            else {
                arr.add(nums2[j]);
                j++;
            }
            k++;
        }
        
        if (i  <  nums1.length) {
            while (i < nums1.length && k < limit) {
                arr.add(nums1[i]);
                i++;
                k++;
            }
        }
        else {
            while (j  <  nums2.length && k < limit) {
                arr.add (nums2[j]);
                j++;
                k++;
            }
        }
        
        k--;
        
        return n%2 == 0 ? (double) (arr.get(k - 1) + arr.get(k)) / 2.0 : (double) arr.get(k);
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums1 = [1,3], nums2 = [2]

Output

x
+
cmd
2.00000

#4 Code Example with Javascript Programming

Code - Javascript Programming


const findMedianSortedArrays = function(A, B) {
  let m = A.length,
    n = B.length;

  if (m > n) {
    return findMedianSortedArrays(B, A);
  }

  let imin = 0,
    imax = m,
    i,
    j;
  while (imin  < = imax) {
    i = (imin + imax) >> 1;
    j = ((m + n + 1) >> 1) - i;
    if (j > 0 && i  <  m && B[j - 1] > A[i]) {
      imin = i + 1;
    } else if (i > 0 && j < n && A[i - 1] > B[j]) {
      imax = i - 1;
    } else {
      if (i === 0) {
        num1 = B[j - 1];
      } else if (j === 0) {
        num1 = A[i - 1];
      } else {
        num1 = Math.max(A[i - 1], B[j - 1]);
      }

      if ((m + n) & 1) {
        return num1;
      }

      if (i === m) {
        num2 = B[j];
      } else if (j === n) {
        num2 = A[i];
      } else {
        num2 = Math.min(A[i], B[j]);
      }
      return (num1 + num2) / 2.0;
    }
  }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums1 = [1,2], nums2 = [3,4]

Output

x
+
cmd
2.50000

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        arr = sorted(nums1 + nums2)
        if len(arr) % 2 == 0: return (arr[len(arr) // 2] + arr[len(arr) // 2 - 1]) / 2
        else: return arr[len(arr) // 2]
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums1 = [1,3], nums2 = [2]

Output

x
+
cmd
2.00000

#6 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _004_MedianOfTwoSortedArrays
    {
        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            int m = nums1.Length + nums2.Length;
            if (m % 2 == 1)
                return FindKth(nums1, 0, nums2, 0, (m + 1) / 2);
            else
                return (FindKth(nums1, 0, nums2, 0, (m + 1) / 2) + FindKth(nums1, 0, nums2, 0, (m + 1) / 2 + 1)) / 2;
        }

        double FindKth(int[] nums1, int startIndex1, int[] nums2, int startIndex2, int k)
        {
            var nums1Left = nums1.Length - startIndex1;
            var nums2Left = nums2.Length - startIndex2;

            if (nums1Left  <  nums2Left) { return FindKth(nums2, startIndex2, nums1, startIndex1, k); }
            if (nums2.Length <= startIndex2) { return nums1[startIndex1 + k - 1]; }
            if (k == 1) { return nums1[startIndex1]  <  nums2[startIndex2] ? nums1[startIndex1] : nums2[startIndex2]; }

            var index1 = k / 2 < nums1Left ? k / 2 : nums1Left;
            var index2 = k - index1  <  nums2Left ? k - index1 : nums2Left;
            if (nums1[index1 + startIndex1 - 1] > nums2[index2 + startIndex2 - 1])
                return FindKth(nums1, startIndex1, nums2, index2 + startIndex2, k - index2);
            else if (nums1[index1 + startIndex1 - 1]  <  nums2[index2 + startIndex2 - 1])
                return FindKth(nums1, index1 + startIndex1, nums2, startIndex2, k - index1);
            else
            {
                if (index1 + index2 == k)
                    return nums1[index1 + startIndex1 - 1];
                return FindKth(nums1, index1 + startIndex1, nums2, index2 + startIndex2, k - index1 - index2);
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums1 = [1,2], nums2 = [3,4]

Output

x
+
cmd
2.50000
Advertisements

Demonstration


Previous
#03 Leetcode Longest Substring Without Repeating Characters Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#05 Leetcode Longest Substring Without Repeating Characters Solution in C, C++, Java, JavaScript, Python, C# Leetcode