Median of Two Sorted Arrays - Practice Coding Problems

Median of Two Sorted Arrays - Problem

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)).

Note: The median is the middle value in an ordered, integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

Input & Output

Example 1 — Even Length

$ Input: nums1 = [1,3], nums2 = [2]

› Output: 2.0

💡 Note: Merged array is [1,2,3] and median is 2.0

Example 2 — Odd Length

$ Input: nums1 = [1,2], nums2 = [3,4]

› Output: 2.5

💡 Note: Merged array is [1,2,3,4] and median is (2 + 3) / 2 = 2.5

Example 3 — Single Element

$ Input: nums1 = [], nums2 = [1]

› Output: 1.0

💡 Note: Merged array is [1] and median is 1.0

Constraints

nums1.length == m
nums2.length == n
0 ≤ m ≤ 1000
0 ≤ n ≤ 1000
1 ≤ m + n ≤ 2000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Setup Binary Search

Search on the smaller array for efficiency

Find Partition Points

Calculate split positions for both arrays

Validate Partition

Check if max(left) ≤ min(right) for both arrays

Calculate Median

Use boundary values to get the median

Key Takeaway

🎯 Key Insight: The median divides all elements into two equal halves. By using binary search to find the right partition, we can achieve O(log(min(m,n))) time complexity without actually merging the arrays.

Asked in

G Google 89 a Amazon 67 M Microsoft 45 🍎 Apple 34 f Facebook 56

The optimal solution uses binary search to find the perfect partition point between two arrays. Instead of merging arrays, we find where to split both arrays so that all left elements ≤ all right elements and both sides have equal counts. This achieves O(log(min(m,n))) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search (Optimal)	O(log(min(m,n)))	O(1)	Use binary search to find the correct partition that divides both arrays into equal halves
Merge and Find	O(m+n)	O(m+n)	Merge both arrays completely, then find the median
Two Pointers Without Extra Space	O(m+n)	O(1)	Use two pointers to traverse both arrays simultaneously until reaching median position

Binary Search (Optimal) — Algorithm Steps

Ensure nums1 is the smaller array for efficiency
Binary search on nums1 to find partition point
Calculate corresponding partition in nums2
Check if partition is valid (left <= right)
Calculate median from partition boundary values

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Search Space

Binary search range on smaller array

Find Partition

Calculate partition points for both arrays

Validate Partition

Check if left elements ≤ right elements

Calculate Median

Get median from partition boundaries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

double solution(int* nums1, int m, int* nums2, int n) {
    // Ensure nums1 is smaller
    if (m > n) {
        return solution(nums2, n, nums1, m);
    }
    
    int left = 0, right = m;
    
    while (left <= right) {
        int partitionX = (left + right) / 2;
        int partitionY = (m + n + 1) / 2 - partitionX;
        
        // Handle edge cases
        int maxLeftX = partitionX == 0 ? INT_MIN : nums1[partitionX - 1];
        int maxLeftY = partitionY == 0 ? INT_MIN : nums2[partitionY - 1];
        
        int minRightX = partitionX == m ? INT_MAX : nums1[partitionX];
        int minRightY = partitionY == n ? INT_MAX : nums2[partitionY];
        
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // Found correct partition
            if ((m + n) % 2 == 0) {
                return ((maxLeftX > maxLeftY ? maxLeftX : maxLeftY) + 
                        (minRightX < minRightY ? minRightX : minRightY)) / 2.0;
            } else {
                return maxLeftX > maxLeftY ? maxLeftX : maxLeftY;
            }
        } else if (maxLeftX > minRightY) {
            right = partitionX - 1;
        } else {
            left = partitionX + 1;
        }
    }
    
    return 0.0;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int nums1[1000], nums2[1000];
    int m = 0, n = 0;
    
    // Parse first array
    char* p = line1 + 1;
    while (*p && *p != ']') {
        if ((*p >= '0' && *p <= '9') || *p == '-') {
            nums1[m++] = atoi(p);
            while (*p && *p != ',' && *p != ']') p++;
        } else p++;
    }
    
    // Parse second array
    p = line2 + 1;
    while (*p && *p != ']') {
        if ((*p >= '0' && *p <= '9') || *p == '-') {
            nums2[n++] = atoi(p);
            while (*p && *p != ',' && *p != ']') p++;
        } else p++;
    }
    
    printf("%g\n", solution(nums1, m, nums2, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log(min(m,n)))

Binary search on the smaller array

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables for partition points

✓ Linear Space

987.7K Views

High Frequency

~25 min Avg. Time

15.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler