Problem Statement
Given two sorted arrays nums1 and nums2 of sizes m and n, find the median of the combined sorted array. The solution must run in O(log(min(m, n))) time complexity.
Examples
Example 1:
Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: Combined sorted array = [1, 2, 3], and median is 2.
Example 2:
Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Explanation: Combined sorted array = [1, 2, 3, 4], and median is (2 + 3) / 2 = 2.5.
Approach
To solve this problem efficiently, we leverage binary search. The key idea is to partition both arrays such that all elements on the left of the partition are less than or equal to all elements on the right.
Steps:
- Identify the shorter of the two arrays. Let it be
nums1with sizem, and the other array benums2with sizen. - Perform binary search on the smaller array.
- Partition the two arrays such that:
- Elements on the left of the partition in both arrays are less than or equal to elements on the right.
- The combined partition sizes on the left and right are equal.
- Calculate the median based on the elements around the partition.
Edge Cases:
- One or both arrays are empty.
- Arrays have different sizes.
C
cCopy code#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) {
if (m > n) return findMedianSortedArrays(nums2, n, nums1, m);
int low = 0, high = m, halfLen = (m + n + 1) / 2;
while (low <= high) {
int i = (low + high) / 2;
int j = halfLen - i;
int maxLeftX = (i == 0) ? INT_MIN : nums1[i - 1];
int minRightX = (i == m) ? INT_MAX : nums1[i];
int maxLeftY = (j == 0) ? INT_MIN : nums2[j - 1];
int minRightY = (j == n) ? INT_MAX : nums2[j];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 == 0)
return (fmax(maxLeftX, maxLeftY) + fmin(minRightX, minRightY)) / 2.0;
else
return fmax(maxLeftX, maxLeftY);
} else if (maxLeftX > minRightY) {
high = i - 1;
} else {
low = i + 1;
}
}
return -1.0; // Invalid input
}
int main() {
int m, n;
printf("Enter size of first array: ");
scanf("%d", &m);
int* nums1 = (int*)malloc(m * sizeof(int));
printf("Enter elements of first array: ");
for (int i = 0; i < m; i++) {
scanf("%d", &nums1[i]);
}
printf("Enter size of second array: ");
scanf("%d", &n);
int* nums2 = (int*)malloc(n * sizeof(int));
printf("Enter elements of second array: ");
for (int i = 0; i < n; i++) {
scanf("%d", &nums2[i]);
}
double result = findMedianSortedArrays(nums1, m, nums2, n);
printf("Median: %.2f\n", result);
free(nums1);
free(nums2);
return 0;
}
C++
cppCopy code#include <bits/stdc++.h>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
int m = nums1.size(), n = nums2.size();
int low = 0, high = m, halfLen = (m + n + 1) / 2;
while (low <= high) {
int i = (low + high) / 2;
int j = halfLen - i;
int maxLeftX = (i == 0) ? INT_MIN : nums1[i - 1];
int minRightX = (i == m) ? INT_MAX : nums1[i];
int maxLeftY = (j == 0) ? INT_MIN : nums2[j - 1];
int minRightY = (j == n) ? INT_MAX : nums2[j];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 == 0)
return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0;
else
return max(maxLeftX, maxLeftY);
} else if (maxLeftX > minRightY) {
high = i - 1;
} else {
low = i + 1;
}
}
return -1.0; // Invalid input
}
int main() {
int m, n;
cout << "Enter size of first array: ";
cin >> m;
vector<int> nums1(m);
cout << "Enter elements of first array: ";
for (int i = 0; i < m; i++) {
cin >> nums1[i];
}
cout << "Enter size of second array: ";
cin >> n;
vector<int> nums2(n);
cout << "Enter elements of second array: ";
for (int i = 0; i < n; i++) {
cin >> nums2[i];
}
double result = findMedianSortedArrays(nums1, nums2);
cout << "Median: " << result << endl;
return 0;
}
Java
javaCopy codeimport java.util.Scanner;
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length)
return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length;
int low = 0, high = m, halfLen = (m + n + 1) / 2;
while (low <= high) {
int i = (low + high) / 2;
int j = halfLen - i;
int maxLeftX = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int minRightX = (i == m) ? Integer.MAX_VALUE : nums1[i];
int maxLeftY = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int minRightY = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 == 0)
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
else
return Math.max(maxLeftX, maxLeftY);
} else if (maxLeftX > minRightY) {
high = i - 1;
} else {
low = i + 1;
}
}
return -1.0; // Invalid input
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter size of first array: ");
int m = sc.nextInt();
int[] nums1 = new int[m];
System.out.println("Enter elements of first array: ");
for (int i = 0; i < m; i++) {
nums1[i] = sc.nextInt();
}
System.out.print("Enter size of second array: ");
int n = sc.nextInt();
int[] nums2 = new int[n];
System.out.println("Enter elements of second array: ");
for (int i = 0; i < n; i++) {
nums2[i] = sc.nextInt();
}
double result = findMedianSortedArrays(nums1, nums2);
System.out.printf("Median: %.2f%n", result);
sc.close();
}
}
Python
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
low, high = 0, m
half_len = (m + n + 1) // 2
while low <= high:
i = (low + high) // 2
j = half_len - i
max_left_x = float('-inf') if i == 0 else nums1[i - 1]
min_right_x = float('inf') if i == m else nums1[i]
max_left_y = float('-inf') if j == 0 else nums2[j - 1]
min_right_y = float('inf') if j == n else nums2[j]
if max_left_x <= min_right_y and max_left_y <= min_right_x:
if (m + n) % 2 == 0:
return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2.0
else:
return max(max_left_x, max_left_y)
elif max_left_x > min_right_y:
high = i - 1
else:
low = i + 1
return -1.0
if __name__ == "__main__":
nums1 = list(map(int, input("Enter first sorted array: ").split()))
nums2 = list(map(int, input("Enter second sorted array: ").split()))
print("Median:", findMedianSortedArrays(nums1, nums2))
C#
csharpCopy codeusing System;
class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.Length > nums2.Length)
return FindMedianSortedArrays(nums2, nums1);
int m = nums1.Length, n = nums2.Length;
int low = 0, high = m, halfLen = (m + n + 1) / 2;
while (low <= high) {
int i = (low + high) / 2;
int j = halfLen - i;
int maxLeftX = (i == 0) ? int.MinValue : nums1[i - 1];
int minRightX = (i == m) ? int.MaxValue : nums1[i];
int maxLeftY = (j == 0) ? int.MinValue : nums2[j - 1];
int minRightY = (j == n) ? int.MaxValue : nums2[j];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 == 0)
return (Math.Max(maxLeftX, maxLeftY) + Math.Min(minRightX, minRightY)) / 2.0;
else
return Math.Max(maxLeftX, maxLeftY);
} else if (maxLeftX > minRightY) {
high = i - 1;
} else {
low = i + 1;
}
}
return -1.0;
}
public static void Main(string[] args) {
Console.Write("Enter the size of the first array: ");
int m = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the elements of the first array (space-separated): ");
int[] nums1 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
Console.Write("Enter the size of the second array: ");
int n = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the elements of the second array (space-separated): ");
int[] nums2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
Solution solution = new Solution();
double result = solution.FindMedianSortedArrays(nums1, nums2);
Console.WriteLine($"Median: {result}");
}
}
JavaScript
javascriptCopy codefunction findMedianSortedArrays(nums1, nums2) {
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length, n = nums2.length;
let low = 0, high = m, halfLen = Math.floor((m + n + 1) / 2);
while (low <= high) {
let i = Math.floor((low + high) / 2);
let j = halfLen - i;
let maxLeftX = (i === 0) ? -Infinity : nums1[i - 1];
let minRightX = (i === m) ? Infinity : nums1[i];
let maxLeftY = (j === 0) ? -Infinity : nums2[j - 1];
let minRightY = (j === n) ? Infinity : nums2[j];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 === 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
} else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (maxLeftX > minRightY) {
high = i - 1;
} else {
low = i + 1;
}
}
throw new Error("Invalid input");
}
// Get user input
const readline = require("readline").createInterface({
input: process.stdin,
output: process.stdout,
});
readline.question("Enter the first sorted array (space-separated): ", input1 => {
const nums1 = input1.split(" ").map(Number);
readline.question("Enter the second sorted array (space-separated): ", input2 => {
const nums2 = input2.split(" ").map(Number);
const median = findMedianSortedArrays(nums1, nums2);
console.log(`Median: ${median}`);
readline.close();
});
});