04.Median of Two Sorted Arrays

📘 LeetCode 4: Median of Two Sorted Arrays

📌 Problem Overview

• Problem Number: 4
• Problem Name: Median of Two Sorted Arrays
• Difficulty: Hard
• Category: Binary Search
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Binary Search algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/4.Median-of-Two-Sorted-Arrays/:

// O(n+m)
double FindMedianSortedArrays2Pointer(int[] nums1, int[] nums2)
{
    int i = 0;
    int j = 0;
    List<int> mergeArr = [];
    while (i < nums1.Length && j < nums2.Length)
    {
        if (nums1[i] < nums2[j])
        {
            mergeArr.Add(nums1[i++]);
        }
        else
        {
            mergeArr.Add(nums2[j++]);
        }
    }
    while (i < nums1.Length) mergeArr.Add(nums1[i++]);
    while (j < nums2.Length) mergeArr.Add(nums2[j++]);
 
    if (mergeArr.Count % 2 == 0)
        return (mergeArr[mergeArr.Count / 2] + mergeArr[mergeArr.Count / 2 + 1]) / 2;
    return mergeArr[mergeArr.Count / 2];
}
 
System.Console.WriteLine(FindMedianSortedArrays2Pointer([1, 3], [2]));
System.Console.WriteLine(FindMedianSortedArrays2Pointer([1, 2], [3, 4]));

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.