Median of Two Sorted Arrays | Dataford Interview Questions

Microsoft Azure analytics can combine two independently sorted streams of numeric measurements. Given two sorted integer arrays, return the median of all values without explicitly merging the arrays.

Formal Specification

Implement find_median_sorted_arrays(nums1, nums2). The inputs are two lists of integers sorted in nondecreasing order. Return the median as a number. If the combined length is odd, return the middle value. If it is even, return the average of the two middle values.

Your algorithm must run in O(log(min(m, n))) time and use O(1) extra space, where m and n are the input lengths.

Constraints

0 <= len(nums1), len(nums2) <= 10^5
1 <= len(nums1) + len(nums2)
-10^9 <= nums1[i], nums2[i] <= 10^9
Both arrays are sorted in nondecreasing order

Function Signature

def find_median_sorted_arrays(nums1, nums2):

Your question is Median of Two Sorted Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem