Median Of Two Sorted Arrays Problem Statement

Given two sorted arrays arr and brr of size n and m respectively, find the median of the array obtained after merging arrays arr and brr (i.e. array of length n + m).

Example

{
"arr": [1, 2],
"brr": [1, 4]
}

Output:

1

Here, arr = [1, 2], brr = [1, 4].\ Array after merging arr and brr = [1, 1, 2, 4].\ Median = Min(1, 2) = 1.

Notes

• Desired complexity is logarithmic and not linear.
• We define median as following:
  • For an array of odd length, the median is the middle element.
  • For an array of even length, the median is the smaller number of the 2 middle elements.

Constraints:

• 2 <= n + m <= 2 * 10⁵
• 1 <= any element of arr and brr <= 10⁹

We have provided two solutions. Throughout the editorial, we will refer to the input arrays as arr and brr and their size as n and m respectively.

Median Of Two Sorted Arrays Solution 1: Linear

• We have to find the median of the merged array obtained after merging 2 sorted arrays.
• We start by traversing the 2 array and keeping track of the minimum element so far.
• As we can see, the answer would be the (n + m) / 2-th minimum element.
• So, we keep on traversing the arrays and move the current pointer for the array having the smaller element, to the next element.
• Finally, when we reach the (n + m) / 2-th element, we return it, as it is our answer.

Time Complexity

O(n + m).

We simply traverse both the arrays simultaneously and keep on checking for the minimum element. We traverse at most one time. Hence, the time complexity is O(n+m).

Auxiliary Space Used

O(1).

We only used a constant amount of extra space.

Space Complexity

O(n + m).

Space used for input: O(n + m).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n + m).

Code For Median Of Two Sorted Arrays Solution 1: Linear

    /*
    Asymptotic complexity in terms of size of input list 'arr' ( = 'n') and 'brr' ( = 'm'):
    * Time: O(n + m).
    * Auxiliary space: O(1).
    * Total space: O(n + m).
    */

    static Integer find_median(ArrayList<Integer> arr, ArrayList<Integer> brr) {
        int l = arr.size() + brr.size();
        int index = 0;

        if(l % 2 == 0) {
            index = l / 2 - 1;
        }

        else {
            index = l / 2;
        }
        int ans = Integer.MAX_VALUE;
        int i = 0, j = 0;

        // We keep on iterating both the lists until we get the index th value.
        // We also make sure we traverse in ascending order.
        while(index >= 0) {

            // If list 'arr' gets exhausted.
            if(i == arr.size()) {
                ans = brr.get(j++);
            }
            // If list 'brr' gets exhausted.
            else if(j == brr.size()) {
                ans = arr.get(i++);
            }
            // Otherwise we get the smaller one and move that the current pointer pointing to that list.
            else {
                if(arr.get(i) > brr.get(j)) {
                    ans = brr.get(j++);
                }
                else {
                    ans = arr.get(i++);
                }
            }
            index--;
        }
        return ans;
    }

Median Of Two Sorted Arrays Solution 2: Optimal

• We have to find the median of the merged array obtained after merging two sorted arrays.
• The goal is to find a partition that divides the combined array in two equal halves (one half having one more element than other in case of odd length) such that the elements in the first half are smaller or equal to the elements in the second half.
• Once we have such a partition, we can simply return the largest element of the first partition which would be the desired output as that would be the element present at the (n + m - 1) / 2-th index in the merged array arr + brr which is the required answer.
• We use binary search to find such a partition and we start by initializing two pointers min_index = 0 and max_index = Math.min(n, m).
• We start iterating over the arrays and compare the last element of partition 1 present in array arr to the first element of partition 2 present in array brr and vice versa. After each comparison, we update min_index and max_index accordingly.
• Finally, we keep on repeating this until min_index <= max_index.
• And we find the median when either we exhaust one of the arrays or none of the if conditions are met.

Example:

• Let's try to find out the median for arr = [1, 2, 5], brr = [1, 2, 3, 4, 5].
• So initially min_index = 0, max_index = n = 3.
• Now we start iterating until min_index <= max_index.
• So, now during first iteration, i = 1 and j = 3
• brr[2] = 3 and arr[1] = 2, so here brr[2] > arr[1] => min_index = i + 1 = 2.
• So during iteration 2, i = 2 and j = 2.
• So in this case we go to the else condition as none of the if conditions are true.
• Hence we return Max(arr[1], brr[1]) = Max(2, 2) = 2.
• So the median is 2.

Time Complexity

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

We use binary search to find the partition. Also, since we are performing binary search until we find the median or we exhaust one of the arrays, time complexity is O(log(min(n, m)).

Auxiliary Space Used

O(1).

We only used a constant amount of extra space.

Space Complexity

O(n + m).

Space used for input: O(n + m).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n + m).

Code For Median Of Two Sorted Arrays Solution 2: Optimal

    /*
    Asymptotic complexity in terms of size of input lists 'arr' ( = 'n') and 'brr' ( = 'm'):
    * Time: O(log(min(n, m))).
    * Auxiliary space: O(1).
    * Total space: O(n + m).
    */

    static Integer find_median(ArrayList<Integer> arr, ArrayList<Integer> brr) {
        int answer = 0;
        int n = arr.size(), m = brr.size();

        // We need to keep the smaller list first to ensure that time complexity is O(log(min(n, m))).
        ArrayList<Integer> min_list = (n < m) ? arr : brr;
        ArrayList<Integer> max_list = (n < m) ? brr : arr;

        int min_index = 0, max_index = Math.min(n, m);
        int i = 0, j = 0;

        while (min_index <= max_index) {
            i = (min_index + max_index) / 2;
            j = ((n + m + 1) / 2) - i;

            // We try to find a partition. We update the \`min_index\` accordingly.
            if (i < min_list.size() && j > 0 && max_list.get(j - 1) > min_list.get(i)) {
                min_index = i + 1;
            }

            // We try to find a partition. We update the \`min_index\` accordingly.
            else if (i > 0 && j < max_list.size() && max_list.get(j) < min_list.get(i - 1)) {
                max_index = i - 1;
            }

            // We got our desired halves, now we simply find the median.
            else {
                if (i == 0) {
                    answer = max_list.get(j - 1);
                }
                else if (j == 0) {
                    answer = min_list.get(i - 1);
                }
                else {
                    answer = Math.max(min_list.get(i - 1), max_list.get(j - 1));
                }
                return answer;
            }
        }
        return answer;
    }

We hope that these solutions to median of two sorted arrays problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.