Median of Two Sorted Arrays | prabhudev.vercel.app

Introduction

Imagine you have two sorted lists of numbers, and you need to find the "middle" value when they’re combined into one sorted list. Sounds simple, right? But doing it efficiently is a classic coding challenge that’s a favorite in interviews! 😄 This guide will walk you through finding the median of two sorted arrays in a way that’s easy to understand, with three approaches from beginner-friendly to super-optimized. Let’s get started! 🚀

Problem Understanding

You’re given two sorted arrays, nums1 (size n) and nums2 (size m), and you need to find the median of the combined array without necessarily merging them. The median is:

The middle number if the total length (n + m) is odd.
The average of the two middle numbers if the total length is even.

Examples

Input: nums1 = [1, 3], nums2 = [2]
- Combined: [1, 2, 3] → Median: 2.0
Input: nums1 = [1, 2], nums2 = [3, 4]
- Combined: [1, 2, 3, 4] → Median: (2 + 3) / 2 = 2.5

Constraints

Arrays are sorted in ascending order.
0 ≤ n, m ≤ 1000
1 ≤ n + m ≤ 2000
Elements can be negative or positive integers.

Pro Tip: Don’t rush to code! First, think about merging the arrays manually to grasp the problem, then optimize step-by-step.

Approach 1: Merge and Sort (Brute Force)

The easiest way is to combine both arrays, sort them, and pick the median. It’s straightforward but not the fastest.

Algorithm

Create a new array merged of size n + m.
Copy all elements from nums1 and nums2 into merged.
Sort merged in ascending order.
If n + m is odd, return the middle element: merged[(n + m) // 2].
If n + m is even, return the average of the two middle elements: (merged[(n + m) // 2 - 1] + merged[(n + m) // 2]) / 2.

Code Example

def findMedianSortedArrays(nums1, nums2):
    merged = nums1 + nums2
    merged.sort()
    total = len(merged)
    
    if total % 2 == 1:
        return float(merged[total // 2])
    else:
        return (merged[total // 2 - 1] + merged[total // 2]) / 2.0
 
# Example
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.0

Complexity

Time Complexity: O((n + m) log(n + m)) due to sorting.
Space Complexity: O(n + m) for the merged array.

Why Use This?

Pros: Super simple to code and understand.
Cons: Sorting makes it slow for large arrays.

Approach 2: Two-Pointer Method (Linear Merge)

Since the arrays are already sorted, we can merge them efficiently using two pointers, like in merge sort, but only up to the median. This is faster than sorting!

Algorithm

Initialize pointers i = 0 for nums1 and j = 0 for nums2.
Calculate the median position: target = (n + m) // 2.
Keep track of the current and previous elements while merging.
Compare nums1[i] and nums2[j]:
- Pick the smaller value, update the current/previous elements, and move the corresponding pointer.
- Repeat until you’ve processed target + 1 elements.
If n + m is odd, return the current element.
If n + m is even, return the average of the previous and current elements.

Code Example

def findMedianSortedArrays(nums1, nums2):
    n, m = len(nums1), len(nums2)
    total = n + m
    target = total // 2
    i, j, count = 0, 0, 0
    prev, curr = 0, 0
    
    while count <= target:
        prev = curr
        if i < n and (j >= m or nums1[i] <= nums2[j]):
            curr = nums1[i]
            i += 1
        else:
            curr = nums2[j]
            j += 1
        count += 1
    
    if total % 2 == 1:
        return float(curr)
    else:
        return (prev + curr) / 2.0
 
# Example
nums1 = [1, 2]
nums2 = [3, 4]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.5

Complexity

Time Complexity: O(n + m) since we merge up to half the elements.
Space Complexity: O(1) as we only use a few variables.

Why Use This?

Pros: Faster than sorting, uses the sorted property of arrays.
Cons: Still linear time, which can be improved.

Approach 3: Binary Search (Optimal)

For the fastest solution, we use binary search to find the perfect partition of the arrays, ensuring the left and right sides balance to give the median. This is advanced but highly efficient.

Algorithm

Make nums1 the smaller array (swap if needed) to minimize binary search range.
Binary search on nums1 to find partition point i (0 to n).
Compute j = (n + m + 1) // 2 - i for nums2.
Get left and right elements around the partition:
- left1 = nums1[i-1] (or -inf if i = 0)
- right1 = nums1[i] (or inf if i = n)
- left2 = nums2[j-1] (or -inf if j = 0)
- right2 = nums2[j] (or inf if j = m)
Check if partition is valid: left1 ≤ right2 and left2 ≤ right1.
If valid:
- For odd n + m, median is max(left1, left2).
- For even n + m, median is (max(left1, left2) + min(right1, right2)) / 2.
If invalid:
- If left1 > right2, move left (right = i - 1).
- If left2 > right1, move right (left = i + 1).

Code Example

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    n, m = len(nums1), len(nums2)
    left, right = 0, n
    
    while left <= right:
        i = (left + right) // 2
        j = (n + m + 1) // 2 - i
        
        left1 = float('-inf') if i == 0 else nums1[i - 1]
        right1 = float('inf') if i == n else nums1[i]
        left2 = float('-inf') if j == 0 else nums2[j - 1]
        right2 = float('inf') if j == m else nums2[j]
        
        if left1 <= right2 and left2 <= right1:
            if (n + m) % 2 == 1:
                return float(max(left1, left2))
            else:
                return (max(left1, left2) + min(right1, right2)) / 2.0
        elif left1 > right2:
            right = i - 1
        else:
            left = i + 1
    
    raise ValueError("Input arrays are not sorted")
 
# Example
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArrays(nums1, nums2))  # Output: 2.0

Complexity

Time Complexity: O(log(min(n, m))) since binary search is on the smaller array.
Space Complexity: O(1) as only a few variables are used.

Why Use This?

Pros: Extremely efficient for large arrays, interview-friendly.
Cons: Complex to understand and implement.

Visualizing the Binary Search Approach

Imagine splitting both arrays into left and right parts:

nums1: [left1 | right1]
nums2: [left2 | right2]

The partition is valid if left1 ≤ right2 and left2 ≤ right1. The median comes from the boundary elements. Drawing this on paper helps clarify the binary search logic!

Which Approach to Choose?

Merge and Sort: Best for quick prototyping or small arrays when simplicity matters.
Two-Pointer: Great for medium-sized arrays, balancing simplicity and efficiency.
Binary Search: Ideal for large arrays or when performance is critical (e.g., production code).

Pro Tips for Interviews

Explain Step-by-Step: Start with the brute force approach to show understanding, then optimize.
Handle Edge Cases:
- Empty arrays (nums1 = [], nums2 = [1])
- Single-element arrays
- Arrays with negative numbers
Visual Aids: Sketch the arrays and pointers/partitions to explain your logic clearly.
Practice: Implement all three approaches to build intuition.

Conclusion 🎯

You’re now ready to tackle the "Median of Two Sorted Arrays" problem with ease: ✅ Understand the problem and its edge cases ✅ Master three approaches: brute force, two-pointer, and binary search ✅ Know the trade-offs and when to use each approach ✅ Impress interviewers with clear explanations and optimized code

This problem is a fantastic way to showcase your problem-solving skills, from simple solutions to advanced optimizations. Keep practicing, and you’ll nail it! 🚀

Stay tuned for more algorithmic adventures and coding tips! 🔥