Median of Two Sorted Arrays Leetcode Solution

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays.

Example:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Understand The Problem

The first step in problem-solving is to understand the problem.

When you read the problem statement, you might immediately have ideas on how to solve it. Do not jump to conclusions and do not let your mind fool you. It’s best not to trust your instincts, and instead, you should go through systematic steps of analyzing the problem. Using a system will dramatically reduce the chance of a mistake.

Note: During the interview, make sure to ask questions before you start solving the problem! Interviewers often give a vague problem definition, and you have to fill in the details by asking questions.

Let’s look at the problem statement:

• There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays.

There is a lot to unpack in every problem statement. First, let’s look at the question overall and then highlight the key parts:

• We are given two sorted arrays, nums1 and nums2.
• The arrays can have different sizes (m and n).
• We need to find the median of the combined array formed by merging nums1 and nums2.

From this information, we can form a basic idea of how the function will look like:

public class MedianOfTwoArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Your code here
    }
}

At this point, we have no idea how to solve anything. However, we do know the input, we do know the output, and we have a basic sense of the algorithm. Let’s dive a little more into the details before we try coming up with a solution…

Let’s analyze the input.

• Sorted Arrays (nums1 and nums2):
  • Could the arrays be empty?
    • Yes, either or both arrays could be empty.
  • Can we expect the arrays to contain only integers?
    • Yes.
  • Are the arrays guaranteed to be sorted in ascending order?
    • Yes.

Note: Notice how simple these questions are. Yet they are so crucial. ANY change in the answers can mean the difference between solving the algorithm and getting it wrong.

We now have a basic understanding of the problem. Let’s try to come up with a solution.

Note: There’s always a chance you miss something – even after carefully examining each detail. Don’t worry. It’s natural. However, you should treat every mistake as an opportunity to improve. Why did you make a mistake? Can you improve your problem-solving system to ensure that you don’t make the same mistake again? That’s the whole point of learning: identify weaknesses, improve your system, and repeat. Iterate, iterate, iterate.

Coming Up With The Solution

Each algorithm problem is different. There is no single approach that will help you solve every problem. However, I recommend starting by creating examples and walking through them.

Let’s start by creating examples:

• Example 1
  • nums1 = [1, 3]
  • nums2 = [2]
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where both arrays have different sizes.
• Example 2
  • nums1 = [1, 2]
  • nums2 = [3, 4]
  • Why this example?
    • This input is nice because it’s simple.
    • It tests the scenario where both arrays have the same size.
• Example 3
  • nums1 = [0, 0]
  • nums2 = [0, 0]
  • Why this example?
    • This input is nice because it tests the scenario where all elements in both arrays are the same.

Note: The number of examples you can go through during the interview will be limited. If you have infinite time, it’s best to try a lot of examples where each examines a specific edge-case. However, you don’t have infinite time in an interview, so you have to strike the balance between speed and accuracy.

As a result of not having a lot of time, let’s pick an example that seems to cover various edge-cases:

• nums1 = [1, 3]
• nums2 = [2]

This example is nice because:

• It’s a simple case with two arrays of different sizes.
• It involves finding the median of the combined array formed by merging nums1 and nums2.
• The result is a decimal value, so we can test the correctness of the algorithm.

Exercise:

With the observations in mind, let’s take the example nums1 = [1, 3] and nums2 = [2] and start thinking about how we can find the median of the combined array formed by merging nums1 and nums2:

• We need to merge the two sorted arrays:
  • We’ll use two pointers to iterate through both arrays simultaneously.
  • We’ll compare the elements pointed by the two pointers and merge them into a new array in sorted order.
  • We’ll continue this process until we reach the middle element(s) of the combined array.

Example Dry Run:

• Let’s say our arrays are nums1 = [1, 3] and nums2 = [2].
• We’ll use two pointers to iterate through both arrays simultaneously.
• At each step, we’ll compare the elements pointed by the two pointers and merge them into a new array in sorted order.
  • At the first step, nums1[0] = 1 and nums2[0] = 2.
    • We’ll merge 1 into the new array.
    • We’ll move the pointer for nums1 to the right.
  • At the second step, nums1[1] = 3 and nums2[0] = 2.
    • We’ll merge 2 into the new array.
    • We’ll merge 3 into the new array.
    • We have reached the end of nums2.
• The merged array is [1, 2, 3].
• The median of the combined array is (2 + 3) / 2 = 2.5.

From this exercise, we have derived an algorithm:

• Initialize two pointers to iterate through both arrays simultaneously.
• Compare the elements pointed by the two pointers and merge them into a new array in sorted order.
• Continue this process until we reach the middle element(s) of the combined array.

– If the combined array has an odd number of elements, return the middle element.

If the combined array has an even number of elements, return the average of the middle two elements.

Here is the algorithm written down:

public class MedianOfTwoArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] mergedArray = new int[m + n];
        int i = 0, j = 0, k = 0;

        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                mergedArray[k++] = nums1[i++];
            } else {
                mergedArray[k++] = nums2[j++];
            }
        }

        while (i < m) {
            mergedArray[k++] = nums1[i++];
        }

        while (j < n) {
            mergedArray[k++] = nums2[j++];
        }

        int length = m + n;
        if (length % 2 == 0) {
            return (mergedArray[length / 2 - 1] + mergedArray[length / 2]) / 2.0;
        } else {
            return mergedArray[length / 2];
        }
    }
}

Note:This process may sound simplistic to you, but there is a powerful lesson here. You can make a simple observation like “We need to merge the two sorted arrays,” and begin by doing the most straightforward thing possible: initializing two pointers to iterate through both arrays simultaneously. Then, let the algorithm evolve from there.

If you are familiar with arrays and binary search, you can see that the algorithm can be solved in O(log(min(m, n))). From this information, we can make further observations:

• To do better, we can solve this in:
  • O(log(min(m, n)))
  • Not all algorithms fit neatly into these time-complexity buckets, but a lot of them do – especially in interviews. As a result, making this type of analysis is helpful to keep moving toward a solution.

Let’s consider each time-complexity and create more insights:

• O(log(min(m, n))) algorithm means we need to perform efficient operations on both arrays.
  • This typically involves binary search or divide and conquer techniques.
  • Additional space complexity might be required if we create new arrays or data structures.
• Binary search is often used to reduce the time complexity of searching problems.

Note: Notice how we can utilize prior knowledge of time-complexity, algorithms, and data structures to generate ideas of how to solve the problem. Make sure to study the Terminology!

Let’s use the O(log(min(m, n))) observation. We have two sorted arrays and need to find the median.

When we consider finding the median of two sorted arrays:

nums1: [1, 3]
nums2: [2]

The median of the combined array is 2.0.

Cool. We found the median, but what does that give us?

We formed a new property for the input: the ability to efficiently search the arrays. Can we somehow exploit this property?

• Let’s begin by repeating what we did above: start by understanding the concept of the median.
  • The median of an array is the middle element if the number of elements is odd, or the average of the two middle elements if the number of elements is even.
• While we found the median, we did find a pattern:
  • We can use binary search to efficiently partition both arrays into two parts such that the elements on the left are smaller than the elements on the right.
  • The median will be either the maximum element on the left side or the minimum element on the right side, depending on whether the total number of elements is odd or even.
• Let’s clarify some of the things we are noticing:
  • We need to partition both arrays such that the number of elements on the left side is equal to or one less than the number of elements on the right side.
  • We need to handle edge cases when one array is empty or when the partition is at the boundaries of one array.

Let’s recap:

1. By understanding the concept of the median, we found a pattern for efficiently partitioning both arrays.
2. Then, by analyzing the pattern, we realized that we need to use binary search to find the partition such that the elements on the left are smaller than the elements on the right.

Note: Leaping to this conclusion is not always straightforward. However, with a lot of practice, and by using the understanding of binary search, you will be able to find these types of insights.

These observations give us an O(log(min(m, n))) algorithm:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0;
        int high = x;

        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                if ((x + y) % 2 == 0) {
                    return (double) (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
                } else {
                    return (double) Math.max(maxX, maxY);
                }
            } else if (maxX > minY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted.");
    }
}

Algorithm Analysis:

• Time Complexity: The algorithm performs binary search on the shorter array, so the time complexity is O(log(min(m, n))), where m and n are the lengths of the input arrays.
• Space Complexity: The algorithm uses a constant amount of extra space, so the space complexity is O(1).

Dry Run:

Let’s dry run the algorithm with an example:

nums1: [1, 3]
nums2: [2]

1. Start by understanding the concept of the median: it’s the middle element if the number of elements is odd, or the average of the two middle elements if the number of elements is even.
2. Partition both arrays such that the number of elements on the left side is equal to or one less than the number of elements on the right side.
3. Calculate the maximum and minimum elements on the left and right sides.
4. If the partition is correct, return the median. Otherwise, adjust the partition using binary search.
5. Continue until the correct partition is found.
6. Return the median of the combined array.

Testing / Reflection

During an interview, if you have the time, you want to test your code by walking through it step-by-step. It’s not uncommon to make a silly mistake.

During practice, you want to reflect on how the solving process went by asking various questions:

• What is the time complexity?
  • O(log(min(m, n)))
• What is the space complexity?
  • O(1)
• What are some interesting observations from this problem?
  • The algorithm efficiently partitions both arrays using binary search to find the median.
  • We need to handle edge cases when one array is empty or when the partition is at the boundaries of one array.
• What are some related problems?
  • There are other variations of this problem like finding the kth element of two sorted arrays.

Reflection is a great step that allows us to “chunk” the learnings from the problem by connecting it to existing ideas.

What else can you think of? Send feedback!

P.S. you can try it @ https://leetcode.com/problems/median-of-two-sorted-arrays/