CodeLab / Problems / #4

4. Median of Two Sorted Arrays

Hard
ArrayBinary SearchDivide & Conquer
Problem Statement
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  // merged = [1,2,3], median = 2
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000  // merged = [1,2,3,4], median = (2+3)/2 = 2.5
My Initial Solution
My first instinct was to merge both arrays, sort the result, then pick the middle element. This is simple and correct, but runs in O((m+n) log(m+n)) time — not optimal for this problem's strict O(log(m+n)) requirement.
Strategy: Merge → Sort → Median
Time: O((m+n) log(m+n))   Space: O(m+n)
High-Level Algorithm Steps
    Multi-Language Code & Execution Simulation
    Strategy:
    Compare Languages:
    Press play to start the simulation.
    Step 0 / 0
    Algorithm Performance & Complexity Chart
    SELECTED APPROACH
    My Answer
    TIME COMPLEXITY
    O((m+n)log(m+n))
    SPACE COMPLEXITY
    O(m+n)
    O((m+n)log(m+n)) — My Answer (Merge & Sort) O(log(min(m,n))) — Binary Search Partition O(log(m+n)) — K-th Element Elimination
    Comprehensive Strategy Matrix
    Strategy Time Space Key Idea / Trade-offs
    My Answer — Merge & Sort O((m+n)log(m+n)) O(m+n) Merge arrays, sort, pick middle. Simple but not optimal. Ignores sorted property.
    AI 1 — Binary Search Partition O(log(min(m,n))) O(1) Binary search on shorter array to find valid partition. Optimal time & space.
    AI 2 — K-th Element Elimination O(log(m+n)) O(log(m+n)) Finds k-th smallest by recursively discarding k/2 elements. Elegant recursion.