Median Of Two Sorted Arrays

 

🚀 LeetCode Hard #1
Median Of Two Sorted Arrays

📌 Problem

Given two sorted arrays nums1 and nums2, return median of combined sorted array. Time Complexity Required: O(log(min(n,m)))

🔥 Intuition

Interviewers are testing if you understand Binary Search on partition instead of merging.

Naive thinking:

Merge arrays
Sort
Return Median

O(n+m)

But interview demands:

O(log(min(n,m)))

✅ Core Idea

A Left Part | A Right Part

B Left Part | B Right Part

Need:

Max(Left)
<=
Min(Right)

🎯 Dry Run

nums1 = [1,3]

nums2 = [2]

Partition gives:

1 | 3

2 |

Left = [1,2]

Right = [3]

Median = 2

☕ Java Solution

public double findMedianSortedArrays(
int[] nums1,
int[] nums2) {

 if(nums1.length > nums2.length)
    return findMedianSortedArrays(
           nums2,nums1);

 int x = nums1.length;
 int y = nums2.length;

 int low=0;
 int high=x;

 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){

         return (
           Math.max(
             maxLeftX,
             maxLeftY
           )
          +
           Math.min(
              minRightX,
              minRightY
           )
         )/2.0;
      }

      return Math.max(
             maxLeftX,
             maxLeftY);
   }

   else if(maxLeftX >
           minRightY){

      high=
      partitionX-1;
   }
   else{

      low=
      partitionX+1;
   }
 }

 return 0;
}

🐍 Python

def findMedianSortedArrays(A,B):

 if len(A)>len(B):
   A,B=B,A

 x=len(A)
 y=len(B)

 low=0
 high=x

 while low<=high:

  px=(low+high)//2
  py=(x+y+1)//2-px

  maxLX=float('-inf') \
       if px==0 else A[px-1]

  minRX=float('inf') \
       if px==x else A[px]

  maxLY=float('-inf') \
       if py==0 else B[py-1]

  minRY=float('inf') \
       if py==y else B[py]

  if maxLX<=minRY \
     and maxLY<=minRX:

      if (x+y)%2==0:
         return (
            max(maxLX,maxLY)
            + min(minRX,minRY)
         )/2

      return max(maxLX,maxLY)

  elif maxLX>minRY:
      high=px-1
  else:
      low=px+1

⚡ JavaScript

function median(A,B){

 if(A.length>B.length)
   return median(B,A);

 let low=0;
 let high=A.length;

 while(low<=high){

  let px=Math.floor(
    (low+high)/2);

  let py=Math.floor(
   (A.length+B.length+1)/2)-px;

  let maxLX=
   px===0?
   Number.MIN_SAFE_INTEGER:
   A[px-1];

  let minRX=
   px===A.length?
   Number.MAX_SAFE_INTEGER:
   A[px];

  let maxLY=
   py===0?
   Number.MIN_SAFE_INTEGER:
   B[py-1];

  let minRY=
   py===B.length?
   Number.MAX_SAFE_INTEGER:
   B[py];

  if(maxLX<=minRY &&
     maxLY<=minRX){

    if((A.length+B.length)%2===0){

      return (
        Math.max(maxLX,maxLY)
       +
        Math.min(minRX,minRY)
      )/2;
    }

    return Math.max(
      maxLX,maxLY);
  }

  if(maxLX>minRY)
      high=px-1;
  else
      low=px+1;
 }

 return -1;
}

🎤 Interview Follow-Ups

• Why not merge arrays?
• Why binary search only smaller array?
• How partition works?
• How handle odd length?
• How handle duplicates?
• Can you derive solution mathematically?

✅ Pattern: Binary Search + Partition