Median of Two Sorted Arrays

Lessons Learned: Array parsing

Question: There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)

Solution

Approach 1: Recursion

This problem can be converted to the problem of finding the kth element, where k is (A’s length + B’ Length)/2.

If any of the two arrays is empty, then the kth element is the non-empty array’s kth element.

If k == 0, the kth element is the first element of A or B.

For normal cases (all other cases), we need to recursively move the pointer at the pace of half of an array length through the following steps:

  1. Calculate the medians m1 and m2 of the input arrays array1[] and array2[] respectively.

  2. If m1 and m2 both are equal then we are done, and return m1 (or m2)

  3. If m1 > m2, then median is present in one of the below two subarrays:

    From first element of array1[] to m1 (array1[][0...m1])

    From m2 to last element of array2[] (array2[][m2…n-1])

  4. If m2 > m1, then median is present in one of the below two subarrays.

    From m1 to last element of array1[] (array1[][m1…n-1])

    From first element of array2[] to m2 (array2[][0...m2])

  5. Repeat the above process until size of both the subarrays becomes 2.

  6. If size of the two arrays is 2 then use below formula to get the median.

    (max(array1[][0], array2[][0]) + min(array1[][1], array2[][1]))/2

See Approach 1

We’re done!


Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.

Subscribe to get full access to the newsletter. Never miss an update.