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:

Image of AssemblyAI tool

Transforming Interviews into Publishable Stories with AssemblyAI

Insightview is a modern web application that streamlines the interview workflow for journalists. By leveraging AssemblyAI's LeMUR and Universal-2 technology, it transforms raw interview recordings into structured, actionable content, dramatically reducing the time from recording to publication.

Key Features:
🎥 Audio/video file upload with real-time preview
🗣️ Advanced transcription with speaker identification
⭐ Automatic highlight extraction of key moments
✍️ AI-powered article draft generation
📤 Export interview's subtitles in VTT format

Read full post

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

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay