Median of Two Sorted Arrays

The problem Median of Two Sorted Arrays is a popular programming problem that asks to find the median of two sorted arrays of integers.

Given two sorted arrays nums1 and nums2 of size m and n respectively, the task is to find the median of the two arrays. The median is defined as the middle element of a sorted array, or the average of the middle two elements if the array has an even number of elements.

The solution should have a time complexity of O(log(m+n)), where m and n are the sizes of the input arrays, and a space complexity of O(1).

This problem is important because it has several real-world applications, such as in statistics, data analysis, and machine learning. It also challenges the programmer to come up with an efficient algorithm to solve the problem, which is a valuable skill in software engineering.

Solution 1: Binary search

This solution uses a binary search approach to find the median of the two sorted arrays. It first calculates the middle two elements of the combined array and then finds the kth element of the combined array, where k is the middle element or the two middle elements.

The findKth function recursively searches for the kth element by dividing the arrays in half and comparing the middle elements. If the middle element of the first array is less than the middle element of the second array, then the first half of the first array and the second half of the second array can be discarded. Otherwise, the opposite halves can be discarded.

Finally, the median is calculated by taking the average of the middle two elements if the combined array has an even number of elements, or simply returning the middle element if the combined array has an odd number of elements.

class Solution {
public:
  double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    int m = nums1.size();
    int n = nums2.size();
    int left = (m + n + 1) / 2;
    int right = (m + n + 2) / 2;
    return (findKth(nums1, 0, nums2, 0, left) +
            findKth(nums1, 0, nums2, 0, right)) /
           2.0;
  }

  int findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
    if (i >= nums1.size())
      return nums2[j + k - 1];
    if (j >= nums2.size())
      return nums1[i + k - 1];
    if (k == 1)
      return min(nums1[i], nums2[j]);

    int mid1 = i + k / 2 - 1;
    int mid2 = j + k / 2 - 1;
    int val1 = mid1 < nums1.size() ? nums1[mid1] : INT_MAX;
    int val2 = mid2 < nums2.size() ? nums2[mid2] : INT_MAX;

    if (val1 < val2) {
      return findKth(nums1, mid1 + 1, nums2, j, k - k / 2);
    } else {
      return findKth(nums1, i, nums2, mid2 + 1, k - k / 2);
    }
  }
};

The time complexity of this solution is O(log(m+n)) because the findKth function uses binary search to eliminate half of the elements in each iteration, resulting in a logarithmic time complexity. The space complexity is O(1).

Solution 2: Merge and find median

One solution is to merge the two sorted arrays into a single sorted array and then find the median of the merged array.

class Solution {
public:
  double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    int m = nums1.size();
    int n = nums2.size();
    int i = 0, j = 0, k = 0;
    vector<int> merged(m + n);

    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 mid = (m + n) / 2;
    if ((m + n) % 2 == 0) {
      return (merged[mid - 1] + merged[mid]) / 2.0;
    } else {
      return merged[mid];
    }
  }
};

This solution has a time complexity of O(m+n) because it needs to merge the two sorted arrays into a single sorted array, and a space complexity of O(m+n) because it needs to store the merged array.

Solution 3: Binary search on shorter array

Another solution is to perform a binary search on the shorter array to find the partition point that separates the two arrays such that the number of elements on the left and right sides of the partition point are equal.

class Solution {
public:
  double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    int m = nums1.size();
    int n = nums2.size();
    if (m > n) {
      return findMedianSortedArrays(nums2, nums1);
    }

    int left = 0, right = m;
    while (left <= right) {
      int partition1 = (left + right) / 2;
      int partition2 = (m + n + 1) / 2 - partition1;

      int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
      int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];
      int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
      int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];

      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
        if ((m + n) % 2 == 0) {
          return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
        } else {
          return max(maxLeft1, maxLeft2);
        }
      } else if (maxLeft1 > minRight2) {
        right = partition1 - 1;
      } else {
        left = partition1 + 1;
      }
    }

    return -1.0;
  }
};

This solution has a time complexity of O(log(min(m, n))) because it performs binary search on the shorter array, and a space complexity of O(1).