Median of Two Sorted Arrays

The problem we’re looking at is called “Median of Two Sorted Arrays.” Essentially, we’re given two sorted arrays of integers, and we need to find the median of the combined array (i.e., the middle value when the two arrays are merged together).

The twist is that we’re not allowed to actually merge the two arrays into one large array, since that would take up too much memory. Instead, we need to come up with a more efficient algorithm that can find the median without actually merging the arrays.

This problem is commonly asked in technical interviews for software engineering roles, especially for candidates with a background in algorithms and data structures.

First, let’s clarify what we mean by the “median” of two sorted arrays. The median is simply the middle value of a sorted list of numbers. If the list has an odd number of values, the median is the middle value; if the list has an even number of values, the median is the average of the two middle values.

Now, let’s talk about the challenge of finding the median of two sorted arrays without merging them. One approach might be to use a binary search algorithm to find the median. We could start by finding the midpoints of both arrays, and comparing the values at those midpoints. Depending on the values, we could narrow down our search to one half of each array, and repeat the process until we find the median.

However, there are a few complications to consider. First, we need to handle the case where the two arrays have different lengths. Second, we need to make sure that we’re always considering the same number of values on each side of the median.

Finally, we need to make sure that our algorithm runs efficiently, since we don’t want it to take too long to find the median.

Lets see one example, let’s say we have two sorted arrays:

nums1 = [1, 3, 5, 7, 9] nums2 = [2, 4, 6, 8, 10]

To find the median of these two arrays, we can follow the binary search approach I mentioned earlier. We start by finding the midpoints of each array:

midpoint1 = len(nums1) // 2 = 2 midpoint2 = len(nums2) // 2 = 2

Now, we compare the values at these midpoints:

nums1[midpoint1] = 5 nums2[midpoint2] = 6

Since 5 < 6, we know that the median of the combined array must be greater than or equal to 5. Therefore, we can discard the first half of nums1 (i.e., the values less than 5) and the second half of nums2 (i.e., the values greater than or equal to 6):

new_nums1 = [5, 7, 9] new_nums2 = [2, 4, 6]

Note that we removed the value 1 from nums1 and the values 8 and 10 from nums2, since those values are on the wrong side of the median. Also note that we discarded one more value from nums1 than from nums2, since the two arrays have different lengths.

We repeat the process with the new arrays:

midpoint1 = len(new_nums1) // 2 = 1 midpoint2 = len(new_nums2) // 2 = 1

nums1[midpoint1] = 7 nums2[midpoint2] = 4

Since 7 > 4, we know that the median of the combined array must be less than or equal to 7. Therefore, we can discard the second half of nums1 and the first half of nums2:

new_nums1 = [5] new_nums2 = [4, 6]

Note that we removed the values 7 and 9 from nums1 and the values 2 and 10 from nums2, since those values are on the wrong side of the median.

At this point, we have narrowed down the possible medians to just one value: 5. We can check that this is indeed the median by calculating the length of the combined array and checking whether it is odd or even.

Since the combined array has length 10 (i.e., 5 values in each array), the median is the average of the two middle values, which are 5 and 6. Therefore, the median of the combined array is:

median = (5 + 6) / 2 = 5.5

And that’s how we can find the median of two sorted arrays without actually merging them!

There are a few different approaches you can use to solve the “Median of Two Sorted Arrays” problem. Here are three:

Merge the arrays and find the median

This is the simplest approach, but it violates the constraint that we’re not allowed to actually merge the two arrays.

However, it’s worth mentioning as a baseline solution, since it helps to clarify what we’re trying to accomplish.

The basic idea is to merge the two arrays into one large array, sort it, and then find the median. Here’s what the code might look like:

function findMedianSortedArrays(nums1, nums2):
    merged = merge(nums1, nums2)
    n = length(merged)
    if n is even:
        return (merged[n/2 - 1] + merged[n/2]) / 2
    else:
        return merged[floor(n/2)]

function merge(nums1, nums2):
    merged = []
    i, j = 0, 0
    while i < length(nums1) and j < length(nums2):
        if nums1[i] < nums2[j]:
            merged.append(nums1[i])
            i++
        else:
            merged.append(nums2[j])
            j++
    if i < length(nums1):
        merged.extend(nums1[i:])
    if j < length(nums2):
        merged.extend(nums2[j:])
    return merged

Median of Two Sorted Arrays using Binary Search:

This is the approach I mentioned earlier. The basic idea is to use a binary search algorithm to narrow down the possible median values.

We start by finding the midpoints of both arrays, and comparing the values at those midpoints.

Depending on the values, we discard one half of each array and repeat the process until we find the median. Here’s what the code might look like:

function findMedianSortedArrays(nums1, nums2):
    n1, n2 = length(nums1), length(nums2)
    if n1 > n2:
        nums1, nums2, n1, n2 = nums2, nums1, n2, n1
    left, right = 0, n1
    while left <= right:
        i = (left + right) / 2
        j = (n1 + n2 + 1) / 2 - i
        if i < n1 and nums2[j-1] > nums1[i]:
            left = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            right = i - 1
        else:
            if i == 0:
                max_of_left = nums2[j-1]
            elif j == 0:
                max_of_left = nums1[i-1]
            else:
                max_of_left = max(nums1[i-1], nums2[j-1])
            if (n1 + n2) % 2 == 1:
                return max_of_left
            if i == n1:
                min_of_right = nums2[j]
            elif j == n2:
                min_of_right = nums1[i]
            else:
                min_of_right = min(nums1[i], nums2[j])
            return (max_of_left + min_of_right) / 2

Median of Two Sorted Arrays using Divide and Conquer

This approach is similar to the binary search approach, but it uses a divide-and-conquer strategy instead of a binary search.

The basic idea is to recursively divide both arrays into two halves, and compare the medians of each half.

Depending on the values, we discard one half of each array and repeat the process until we find the median. Here’s what the code might look like:

function findMedianSortedArrays(nums1, nums2):
    m, n = length(nums1), length(nums2)
    if m > n:
        nums1, nums2, m, n = nums2, nums1, n, m
    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and nums2[j-1] > nums1[i]:
            imin = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            imax = i - 1
        else:
            if i == 0:
                max_of_left = nums2[j-1]
            elif j == 0:
                max_of_left = nums1[i-1]
            else:
                max_of_left = max(nums1[i-1], nums2[j-1])
            if (m + n) % 2 == 1:
                return max_of_left
            if i == m:

Which One is better and why?

Each of the three solutions has its own strengths and weaknesses. Here’s a brief comparison of the three approaches:

Merge the arrays and find the median:

• Simple and easy to implement
• Violates the constraint that we’re not allowed to merge the two arrays
• Has a time complexity of O((m+n)log(m+n)), where m and n are the lengths of the input arrays. This is because we need to merge the two arrays, which takes O(m+n) time, and then sort the merged array, which takes O((m+n)log(m+n)) time.

Binary search:

• More complex than the first solution, but still relatively easy to understand and implement
• Does not violate the constraint that we’re not allowed to merge the two arrays
• Has a time complexity of O(log(min(m, n))), where m and n are the lengths of the input arrays. This is because we’re essentially performing a binary search on the shorter of the two arrays, and each iteration of the search cuts the size of the shorter array in half.

Divide and conquer:

• More complex than the first two solutions, and may be more difficult to understand and implement correctly
• Does not violate the constraint that we’re not allowed to merge the two arrays
• Has a time complexity of O(log(min(m, n))), the same as the binary search approach.

Median of Two Sorted Arrays: Python Solution

def findMedianSortedArrays(nums1, nums2):
    m, n = len(nums1), len(nums2)
    if m > n:
        nums1, nums2, m, n = nums2, nums1, n, m
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        if i < m and nums2[j-1] > nums1[i]:
            imin = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            imax = i - 1
        else:
            if i == 0:
                max_of_left = nums2[j-1]
            elif j == 0:
                max_of_left = nums1[i-1]
            else:
                max_of_left = max(nums1[i-1], nums2[j-1])
            if (m + n) % 2 == 1:
                return max_of_left
            if i == m:
                min_of_right = nums2[j]
            elif j == n:
                min_of_right = nums1[i]
            else:
                min_of_right = min(nums1[i], nums2[j])
            return (max_of_left + min_of_right) / 2

Median of Two Sorted Arrays: Java Solution

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    if (m > n) {
        int[] temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        int tmp = m;
        m = n;
        n = tmp;
    }
    int imin = 0, imax = m, half_len = (m + n + 1) / 2;
    while (imin <= imax) {
        int i = (imin + imax) / 2;
        int j = half_len - i;
        if (i < m && nums2[j-1] > nums1[i]) {
            imin = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            imax = i - 1;
        } else {
            int max_of_left;
            if (i == 0) {
                max_of_left = nums2[j-1];
            } else if (j == 0) {
                max_of_left = nums1[i-1];
            } else {
                max_of_left = Math.max(nums1[i-1], nums2[j-1]);
            }
            if ((m + n) % 2 == 1) {
                return max_of_left;
            }
            int min_of_right;
            if (i == m) {
                min_of_right = nums2[j];
            } else if (j == n) {
                min_of_right = nums1[i];
            } else {
                min_of_right = Math.min(nums1[i], nums2[j]);
            }
            return (max_of_left + min_of_right) / 2.0;
        }
    }
    return 0.0;
}

Median of Two Sorted Arrays: JavaScript Solution

function findMedianSortedArrays(nums1, nums2) {
    let m = nums1.length;
    let n = nums2.length;
    if (m > n) {
        let temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        let tmp = m;
        m = n;
        n = tmp;
    }
    let imin = 0, imax = m, half_len = Math.floor((m + n + 1) / 2);
    while (imin <= imax) {
        let i = Math.floor((imin + imax) / 2);
        let j = half_len - i;
        if (i < m && nums2[j-1] > nums1[i]) {
            imin = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            imax = i - 1;
        } else {
            let max_of_left;
            if (i == 0) {
                max_of_left = nums2[j-1];
            } else if (j == 0) {
                max_of_left = nums1[i-1];
            } else {
                max_of_left = Math.max(nums1[i-1], nums2[j-1]);
            }
            if ((m + n) % 2 === 1) {
                return max_of_left;
            }
            let min_of_right;
            if (i == m) {
                min_of_right = nums2[j];
            } else if (j == n) {
                min_of_right = nums1[i];
            } else {
                min_of_right = Math.min(nums1[i], nums2[j]);
            }
            return (max_of_left + min_of_right) / 2;
        }
    }
    return 0;
}

Median of Two Sorted Arrays: Ruby Solution

def find_median_sorted_arrays(nums1, nums2)
    m = nums1.length
    n = nums2.length
    if m > n
        nums1, nums2 = nums2, nums1
        m, n = n, m
    end
    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and nums2[j-1] > nums1[i]
            imin = i + 1
        elsif i > 0 and nums1[i-1] > nums2[j]
            imax = i - 1
        else
            if i == 0
                max_of_left = nums2[j-1]
            elsif j == 0
                max_of_left = nums1[i-1]
            else
                max_of_left = [nums1[i-1], nums2[j-1]].max
            end
            if (m + n) % 2 == 1
                return max_of_left
            end
            if i == m
                min_of_right = nums2[j]
            elsif j == n
                min_of_right = nums1[i]
            else
                min_of_right = [nums1[i], nums2[j]].min
            end
            return (max_of_left + min_of_right) / 2.0
        end
    end
    return 0.0
end

The basic idea of the binary search solution is to partition the two input arrays in such a way that the median of the combined array can be found by looking at only the elements on either side of the partition. Specifically, we want to find two indices i and j such that:

• All elements to the left of i and j (including i and j) are less than or equal to the median
• All elements to the right of i and j (including i and j) are greater than or equal to the median

Once we’ve found the correct values of i and j, we can calculate the median using the following formula:

• If m + n is odd, the median is the maximum of the elements to the left of the partition (i.e., max(nums1[i-1], nums2[j-1]))
• If m + n is even, the median is the average of the maximum of the elements to the left of the partition and the minimum of the elements to the right of the partition (i.e., (max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) / 2)

The key to the binary search solution is figuring out how to choose the values of i and j at each step. We start by initializing imin and imax to 0 and m, respectively, where m is the length of the shorter input array. We then use a while loop to perform the binary search:

• At each iteration of the loop, we compute the value of i as the midpoint between imin and imax (i.e., i = (imin + imax) / 2)
• We compute j as half_len – i, where half_len is the desired position of the partition in the combined array (i.e., half_len = (m + n + 1) / 2)
• If nums2[j-1] > nums1[i], we need to move the partition to the right, so we set imin = i + 1
• If nums1[i-1] > nums2[j], we need to move the partition to the left, so we set imax = i – 1
• If neither of the above conditions is true, we’ve found the correct values of i and j, and we can use the formula above to calculate the median

We repeat this process until we’ve found the correct values of i and j, or until imin > imax (which indicates that we’ve gone too far and need to terminate the loop).