The Question

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the combined sorted array. The solution must achieve an overall runtime complexity of $O(\log(m+n))$ or better. You may assume both arrays are sorted in non-decreasing order and are not both empty.

Java

Binary Search

Questions & Insights

Clarifying Questions

What are the constraints on the sizes of the input arrays?

Assumption: Arrays

A

B

can have lengths

n, m

up to

10^6

. The solution must be more efficient than

O(n+m)

Can the arrays contain duplicate values or be empty?

Assumption: Both arrays are sorted in non-decreasing order. One array can be empty, but not both.

What is the expected time and space complexity?

Assumption: The goal is

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

time complexity and

O(1)

auxiliary space.

How should the result be returned for even vs. odd total elements?

Assumption: If the total number of elements is odd, return the middle element. If even, return the average of the two middle elements as a double.

Thinking Process

Binary Search on Partitions: Instead of merging the arrays, we aim to find a partition point in both arrays such that all elements to the left of the partition are less than or equal to all elements to the right.

Partition Logic: Let

n = len(A)

and

m = len(B)

. We partition

A

t index

i

and

B

at index

j

such that

i + j = (n + m + 1) / 2

. This ensures the left half has the same number of elements as the right half (or one more if the total is odd).

Validation Criteria: A partition is valid if

A[i-1] \le B[j]

and

B[j-1] \le A[i]

. If

A[i-1] > B[j]

, we must move the partition in

A

to the left (decrease

i

B[j-1] > A[i]

, we move it to the right (increase

i

Handling Boundaries: Use

-\infty

for left-side elements if the partition index is 0, and

+\infty

for right-side elements if the partition index is at the array's end.

Implementation Breakdown

Problem Set

Functional Requirements: Find the median of two sorted arrays of different sizes.

Time Complexity: Must be

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

Space Complexity: Must be

O(1)

Input: Two integer arrays, nums1 and nums2.

Output: A double representing the median.

Approach

Algorithm: Binary Search on the partition index.

Data Structure: Arrays.

Complexity:

Time:

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

- we perform binary search on the smaller array.

Space:

O(1)

- no additional data structures proportional to input size are used.

Implementation

Wrap Up

Advanced Topics

Handling Large Scale Data: If arrays are too large to fit in memory, we can adapt this using a distributed approach (e.g., MapReduce) or by performing the binary search via remote range queries over a distributed file system.

Readability vs. Performance: While the

O(\log n)

approach is optimal, for very small arrays (e.g.,

n+m < 100

), a simple

O(n+m)

merge might be faster due to cache locality and lower constant factors.

K-th Element Generalization: This problem is a specific case of finding the

k

-th smallest element in two sorted arrays. The logic can be generalized to return any

k

-th element in

O(\log k)

time.