Summary of "BS-21. Median of two Sorted Arrays of Different Sizes | Binary Search Approach With Intuition"

Summary of “BS-21. Median of two Sorted Arrays of Different Sizes | Binary Search Approach With Intuition”

This video explains the problem of finding the median of two sorted arrays of possibly different sizes using an optimized binary search approach. It covers the intuition behind the problem, the reasoning for applying binary search, and the step-by-step methodology for solving it efficiently.

Main Ideas and Concepts

Problem Definition

Given two sorted arrays (possibly of different sizes), find the median of their combined elements.
Median definition depends on whether the total number of elements is even or odd:
- Even total elements: Median is the average of the two middle elements.
- Odd total elements: Median is the middle element.

Naive Approach

Merge both arrays and find the median directly.
Time complexity: O(n₁ + n₂), which is inefficient for large inputs and may cause time limit exceeded errors.

Optimized Approach Using Binary Search

Leverage the sorted property of arrays to apply binary search.
Key insight: partition both arrays into left and right halves such that:
- The left half contains half (or half + 1 if odd) of the total elements.
- All elements in the left half are less than or equal to all elements in the right half.
This partitioning creates a “symmetry” where the median can be found by comparing boundary elements.

Detailed Methodology / Instructions

1. Understanding the Partitioning

Let total elements = n₁ + n₂.
Number of elements needed on the left side = (n₁ + n₂ + 1) / 2 (handles both even and odd).
Choose a partition index mid1 in the smaller array (binary search is applied here).
Partition index in the second array mid2 = total elements on left - mid1.

2. Checking Validity of Partition (Symmetry Check)

Define:

L1 = element just before partition in array 1 (or -∞ if none).
L2 = element just before partition in array 2 (or -∞ if none).
R1 = element just after partition in array 1 (or +∞ if none).
R2 = element just after partition in array 2 (or +∞ if none).

A partition is valid if:

L1 <= R2 and L2 <= R1.

If not valid:

If L1 > R2, move partition in array 1 to the left (reduce high).
Else if L2 > R1, move partition in array 1 to the right (increase low).

3. Calculating Median

If total elements are odd:
- Median = max(L1, L2).
If total elements are even:
- Median = (max(L1, L2) + min(R1, R2)) / 2.

4. Binary Search Implementation

Always perform binary search on the smaller array to minimize time complexity.
Initialize low = 0, high = n₁ (size of smaller array).
Loop until valid partition is found:
- Calculate mid1 = (low + high) / 2.
- Calculate mid2 = (n₁ + n₂ + 1) / 2 - mid1.
- Retrieve L1, L2, R1, R2 with boundary checks.
- Check partition validity and adjust low and high accordingly.
Return median based on the partition found.

5. Handling Edge Cases

If partition index is 0, consider left element as -∞ (no elements on left).
If partition index equals array length, consider right element as +∞ (no elements on right).

Time and Space Complexity

Time Complexity: O(log(min(n₁, n₂))) — binary search on the smaller array.
Space Complexity: O(1) — no extra space used besides variables.

Additional Notes

The problem is solved by focusing on the “symmetry” of partitioning arrays rather than merging them.
The approach works uniformly for both even and odd total lengths.
The video explains the intuition behind why certain partitions are invalid by comparing cross-boundary elements.
Code is implemented in C++ with notes for Java, Python, and JavaScript.
The speaker emphasizes understanding the problem deeply before jumping to code.

Speakers / Sources

Primary Speaker: The instructor/presenter of the Strivers A to Z DSA course (name not explicitly mentioned).
The video is part of the “Strivers A to Z DSA course” playlist.

This summary captures the core ideas, methodology, and reasoning behind the binary search approach to find the median of two sorted arrays of different sizes as explained in the video.

Share this summary

Is the summary off?

If you think the summary is inaccurate, you can reprocess it with the latest model.

Summarize another video

Summary of "BS-21. Median of two Sorted Arrays of Different Sizes | Binary Search Approach With Intuition"