Problem

You are managing two different departments within a company that have collected sales data. The first department (hardware) has recorded sales figures for ‘h’ number of products, while the second department (software) has recorded sales figures for ’s number of products. Both sets of data are sorted in ascending order. you are asked to find the median of these two sorted sales data (arrays)

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [10,30], nums2 = [20]
Output: 20.00000
Explanation: merged array = [10,20,30] and median is 20.

Example 2:

Input: nums1 = [10,20], nums2 = [30,40]
Output: 25.00000
Explanation: merged array = [10,20,30,40] and median is (20 + 30) / 2 = 25.

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Java Solution

class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    final int n1 = nums1.length;
    final int n2 = nums2.length;
    if (n1 > n2)
      return findMedianSortedArrays(nums2, nums1);

    int l = 0;
    int r = n1;

    while (l <= r) {
      final int partition1 = (l + r) / 2;
      final int partition2 = (n1 + n2 + 1) / 2 - partition1;
      final int maxLeft1 = partition1 == 0 ? Integer.MIN_VALUE : nums1[partition1 - 1];
      final int maxLeft2 = partition2 == 0 ? Integer.MIN_VALUE : nums2[partition2 - 1];
      final int minRight1 = partition1 == n1 ? Integer.MAX_VALUE : nums1[partition1];
      final int minRight2 = partition2 == n2 ? Integer.MAX_VALUE : nums2[partition2];
      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
        return (n1 + n2) % 2 == 0
            ? (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) * 0.5
            : Math.max(maxLeft1, maxLeft2);
      else if (maxLeft1 > minRight2)
        r = partition1 - 1;
      else
        l = partition1 + 1;
    }

    throw new IllegalArgumentException();
  }
}
  1. Choose the smaller array as nums1 so that the problem is simpler with less log(n) complexity.
  2. Use Binary Search (BS) to partition the smallest array.
  3. Now we calculate the position of partition in the larger array (nums2) having fetched the smaller one.
  4. Find the four important numbers - maxSize - left and right of partition in the two arrays.
  5. If maxSizeLeft <= minSizeRight and maxSizeLeft2 <= minSizeRight2, then the partition of both arrays is correct, if not, adjust the partition of nums1. If maxLeftX > minRightY, move the BS partition to the left; if maxLeftY > minRightX, move the BS partition to the right.
  6. When the correct partition is found, calculate the median based on the length of the merged array, even or odd.

C++ Solution

class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    const int n1 = nums1.size();
    const int n2 = nums2.size();
    if (n1 > n2)
      return findMedianSortedArrays(nums2, nums1);

    int l = 0;
    int r = n1;

    while (l <= r) {
      const int partition1 = (l + r) / 2;
      const int partition2 = (n1 + n2 + 1) / 2 - partition1;
      const int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
      const int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
      const int minRight1 = partition1 == n1 ? INT_MAX : nums1[partition1];
      const int minRight2 = partition2 == n2 ? INT_MAX : nums2[partition2];
      if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
        return (n1 + n2) % 2 == 0
                   ? (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5
                   : max(maxLeft1, maxLeft2);
      else if (maxLeft1 > minRight2)
        r = partition1 - 1;
      else
        l = partition1 + 1;
    }

    throw;
  }
};
  1. Choose the smaller array as nums1 so that the problem is simpler with less log(n) complexity.
  2. Use Binary Search (BS) to partition the smallest array.
  3. Now we calculate the position of partition in the larger array (nums2) having fetched the smaller one.
  4. Find the four important numbers - maxSize - left and right of partition in the two arrays.
  5. If maxSizeLeft <= minSizeRight and maxSizeLeft2 <= minSizeRight2, then the partition of both arrays is correct, if not, adjust the partition of nums1. If maxLeftX > minRightY, move the BS partition to the left; if maxLeftY > minRightX, move the BS partition to the right.
  6. When the correct partition is found, calculate the median based on the length of the merged array, even or odd.

Python Solution

class Solution:
  def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
    n1 = len(nums1)
    n2 = len(nums2)
    if n1 > n2:
      return self.findMedianSortedArrays(nums2, nums1)

    l = 0
    r = n1

    while l <= r:
      partition1 = (l + r) // 2
      partition2 = (n1 + n2 + 1) // 2 - partition1
      maxLeft1 = -2**31 if partition1 == 0 else nums1[partition1 - 1]
      maxLeft2 = -2**31 if partition2 == 0 else nums2[partition2 - 1]
      minRight1 = 2**31 - 1 if partition1 == n1 else nums1[partition1]
      minRight2 = 2**31 - 1 if partition2 == n2 else nums2[partition2]
      if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
        return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5 if (n1 + n2) % 2 == 0 else max(maxLeft1, maxLeft2)
      elif maxLeft1 > minRight2:
        r = partition1 - 1
      else:
        l = partition1 + 1
  1. Choose the smaller array as nums1 so that the problem is simpler with less log(n) complexity.
  2. Use Binary Search (BS) to partition the smallest array.
  3. Now we calculate the position of partition in the larger array (nums2) having fetched the smaller one.
  4. Find the four important numbers - maxSize - left and right of partition in the two arrays.
  5. If maxSizeLeft <= minSizeRight and maxSizeLeft2 <= minSizeRight2, then the partition of both arrays is correct, if not, adjust the partition of nums1. If maxLeftX > minRightY, move the BS partition to the left; if maxLeftY > minRightX, move the BS partition to the right.
  6. When the correct partition is found, calculate the median based on the length of the merged array, even or odd.

JavaScript Solution

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    
    const x = nums1.length;
    const y = nums2.length;
    let low = 0;
    let high = x;
    
    while (low <= high) {
        const partitionX = Math.floor((low + high) / 2);
        const partitionY = Math.floor((x + y + 1) / 2) - partitionX;
        
        const maxLeftX = (partitionX === 0) ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
        const minRightX = (partitionX === x) ? Number.POSITIVE_INFINITY : nums1[partitionX];
        
        const maxLeftY = (partitionY === 0) ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
        const minRightY = (partitionY === y) ? Number.POSITIVE_INFINITY : nums2[partitionY];
        
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }    
    return 0;
}
  1. Choose the smaller array as nums1 so that the problem is simpler with less log(n) complexity.
  2. Use Binary Search (BS) to partition the smallest array.
  3. Now we calculate the position of partition in the larger array (nums2) having fetched the smaller one.
  4. Find the four important numbers - maxSize - left and right of partition in the two arrays.
  5. If maxSizeLeft <= minSizeRight and maxSizeLeft2 <= minSizeRight2, then the partition of both arrays is correct, if not, adjust the partition of nums1. If maxLeftX > minRightY, move the BS partition to the left; if maxLeftY > minRightX, move the BS partition to the right.
  6. When the correct partition is found, calculate the median based on the length of the merged array, even or odd.

In a real-world scenario, imagine you are managing two different departments within a company that have collected sales data. The first department (nums1) has recorded sales figures for ’m’ number of products, while the second department (nums2) has recorded sales figures for ’n’ number of products. Both sets of data are sorted in ascending order.

To solve this problem efficiently while maintaining a logarithmic time complexity (O(log(m+n))), you would need to implement an algorithm that leverages properties of sorted arrays and binary search techniques. This ensures not only efficiency but also scalability when dealing with larger datasets.

The key steps in finding the median could involve understanding how medians are calculated for odd and even numbers of observations, as well as considering the impact of the different sizes (’m’ vs ’n’) of the two input arrays on the final calculation.

By efficiently merging these two sorted arrays and calculating their median, you can provide insights that were previously unavailable when each department operated independently. This could lead to more informed decision-making at an organizational level.