DEV Community

Cover image for 4. Median of Two Sorted Arrays
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

Hard

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

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

Example 1:

  • Input: nums1 = [1,3], nums2 = [2]
  • Output: 2.00000
  • Explanation: merged array = [1,2,3] and median is 2.

Example 2:

  • Input: nums1 = [1,2], nums2 = [3,4]
  • Output: 2.50000
  • Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

  • Input: nums1 = [0,0], nums2 = [0,0]
  • Output: 0.00000

Example 4:

  • Input: nums1 = [], nums2 = [1]
  • Output: 1.00000

Example 5:

  • Input: nums1 = [2], nums2 = []
  • Output: 2.00000

Constraints:

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

Solution:

To solve this problem, we can follow these steps:

Let's implement this solution in PHP: 4. Median of Two Sorted Arrays

<?php
// Example usage:
$nums1 = [1, 3];
$nums2 = [2];
echo findMedianSortedArrays($nums1, $nums2) . "\n"; // Output: 2.00000

$nums1 = [1, 2];
$nums2 = [3, 4];
echo findMedianSortedArrays($nums1, $nums2) . "\n"; // Output: 2.50000

$nums1 = [0, 0];
$nums2 = [0, 0];
echo findMedianSortedArrays($nums1, $nums2) . "\n"; // Output: 0.00000

$nums1 = [];
$nums2 = [1];
echo findMedianSortedArrays($nums1, $nums2) . "\n"; // Output: 1.00000

$nums1 = [2];
$nums2 = [];
echo findMedianSortedArrays($nums1, $nums2) . "\n"; // Output: 2.00000
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Partitioning the Arrays:

    • Ensure that nums1 is the smaller array. This simplifies the binary search since we're always partitioning the smaller array.
    • Initialize imin, imax, and half_len.
    • Use binary search to partition nums1 and nums2 such that all elements on the left of the partition are less than or equal to all elements on the right of the partition.
  2. Checking Partitions:

    • Adjust the binary search range based on comparisons between the elements around the partitions.
    • If the partitions are correctly placed, calculate the median based on the maximum elements on the left side and the minimum elements on the right side.
  3. Returning the Median:

    • If the total number of elements is odd, the median is the maximum element on the left side.
    • If the total number of elements is even, the median is the average of the maximum element on the left side and the minimum element on the right side.

This solution ensures that the overall run time complexity is (O(\log(m+n))).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay