• Brute force: Merge both arrays, then compute the median.

  • Time complexity: O(m + n)
  • Space complexity: O(m + n)

• Better (two pointers): Avoid merging. Use two pointers and track the elements at indices n/2 and n/2 - 1.

  • Time complexity: O(m + n)
  • Space complexity: O(1)

  class Solution
  {
  public:
      double median(vector<int> &arr1, vector<int> &arr2)
      {
          int n1 = arr1.size();
          int n2 = arr2.size();
          int n = n1 + n2;
          int ind1 = n / 2, ind2 = ind1 - 1, cnt = 0;
          int i = 0, j = 0, e1 = -1, e2 = -1;
          while (i < n1 && j < n2)
          {
              if (arr1[i] < arr2[j])
              {
                  if (cnt == ind1)
                      e1 = arr1[i];
                  if (cnt == ind2)
                      e2 = arr1[i];
                  cnt++;
                  i++;
              }
              else
              {
                  if (cnt == ind1)
                      e1 = arr2[j];
                  if (cnt == ind2)
                      e2 = arr2[j];
                  cnt++;
                  j++;
              }
          }
          while (i < n1)
          {
              if (cnt == ind1)
                  e1 = arr1[i];
              if (cnt == ind2)
                  e2 = arr1[i];
              i++;
              cnt++;
          }
          while (j < n2)
          {
              if (cnt == ind1)
                  e1 = arr2[j];
              if (cnt == ind2)
                  e2 = arr2[j];
              j++;
              cnt++;
          }
          if (n % 2 == 1)
              return (double)e1;
          return (double)((double)(e1 + e2)) / 2.0;
      }
  
  

• Optimal (binary search partition): Use binary search to partition the two arrays so that every element in the left half is ≤ every element in the right half.

  • Time complexity: O(log(min(m, n)))
  • Space complexity: O(1)

class Solution2
{
public:
    double median(vector<int> &arr1, vector<int> &arr2)
    {
        int n1 = arr1.size();
        int n2 = arr2.size();
        if (n1 > n2)
            return median(arr2, arr1);
        int n = n1 + n2;
        int low = 0, high = n1;
        int leftHalf = (n + 1) / 2;

        while (low <= high)
        {
            int mid1 = (low + high) >> 1; 
            int mid2 = leftHalf - mid1; 
            int l1 = INT_MIN, l2 = INT_MIN, r1 = INT_MAX, r2 = INT_MAX;
            if (mid1 < n1)
                r1 = arr1[mid1];
            if (mid2 < n2)
                r2 = arr2[mid2];
            if (mid1 - 1 >= 0)
                l1 = arr1[mid1 - 1];
            if (mid2 - 1 >= 0)
                l2 = arr2[mid2 - 1];
            if (l1 <= r2 && l2 <= r1)
            {
                if (n % 2 == 1)
                    return max(l1, l2);
                return (max(l1, l2) + min(r1, r2)) / 2.0;
            }
            else if (l1 > r2)
            {
                high = mid1 - 1;
            }
            else
                low = mid1 + 1;
        }
        return 0;
    }
};