4. Median of Two Sorted Arrays

Problem Description

The problem presents us with two sorted arrays, nums1 and nums2, with sizes m and n respectively. Our task is to find the median of these two sorted arrays combined. The median is the value that separates a dataset into two halves. In other words, half of the numbers in the dataset are less than the median, and half are greater than it. If there is an odd number of observations, the median is the middle number. If there is an even number of observations, the median is the average of the two middle numbers.

Given the arrays are already sorted, if we could merge them, finding the median would be trivial: take the middle value or the average of the two middle values. However, merging the arrays may not be efficient, specifically for large sizes of m and n. Therefore, we are asked to find an efficient approach with a runtime complexity of O(log (m+n)), which suggests that we should not actually merge the arrays, and instead, consider an algorithm similar in efficiency to binary search.

Intuition

The intuition behind the solution is to use a binary search due to the sorted nature of the arrays and the requirement of a O(log (m+n)) runtime complexity. To find the median of two sorted arrays, we could approach the problem as finding the 'kth' smallest element, where 'k' would be the median position in the combined array, which is (m+n+1)//2 for the lower median and (m+n+2)//2 for the upper median.

The solution uses a binary search which is applied recursively by defining a helper function f(i, j, k) where i and j are the current indices in nums1 and nums2 respectively, and k is the position of the element we are looking for in the merged array. If one of the arrays is exhausted (i >= m or j >= n), the kth element is directly found in the other array. When the position k is 1, we simply take the minimum between the current elements pointed by i and j.

The main trick is dividing the problem in half at each step: We pick the middle element position (p = k // 2) from the remaining elements to compare in each array and reduce the problem size by p, discarding the smaller half each time. The variable x corresponds to the element at position i + p - 1 in nums1 unless this position is outside the array bounds (in which case we use infinity), and similarly for y in nums2. We recursively call function f with adjusted indices based on which half we are discarding.

Finally, since the median can be a single middle value (for odd total length) or the average of two middle values (for even total length), the solution calls the helper function twice, for the kth and (k+1)th positions, and returns their average.

Note: The use of inf in the solution assumes a Python environment where inf represents an infinite number, which serves as a stand-in when comparing out-of-bounds indices in one of the arrays.

Learn more about Binary Search and Divide and Conquer patterns.

Solution Approach

The solution employs a divide and conquer strategy which is effectively a tailored binary search across two arrays to find the median.

Here's a step by step breakdown of the approach:

1. Define a Helper Function: The f(i, j, k) function serves as the core for the binary search strategy, by recursively finding the kth smallest element in the combined array made up by nums1 and nums2. Parameters i and j are the starting points in nums1 and nums2, respectively, and k is the number of steps away from the starting points to the target element in the merged array.

2. Base Cases: The helper function has three essential base cases:

   • If i or j run past the length of their respective arrays (i >= m or j >= n), the answer is found in the other array. This is because once one array is exhausted, the remaining kth element must be in the other array.
   • If k is 1, we can't divide the search space any smaller, so we just return the minimum of the two element values that i and j are pointing at.

3. Recursive Case: For the recursive case, we divide the remaining search space (k) in two by setting p = k // 2. We then find the potential pth element in both arrays (x and y) if those positions are in bounds.

4. Compare and Eliminate: We compare these potential candidates, x and y, to eliminate the half of the search space that can't possibly contain the kth smallest element. If x is smaller, we know that anything before and including x in nums1 cannot contain the kth smallest, so we move the search space past x, by calling f(i + p, j, k - p). Similarly, if y is smaller, we call f(i, j + p, k - p).

5. Find Medians: Once we've established our helper function, we use it to find the medians depending on whether the combined length of nums1 and nums2 is odd or even:

   • For an odd combined length, the median is at position (m + n + 1) // 2, so only one call to f(0, 0, (m + n + 1) // 2) is necessary.
   • For an even combined length, we call the function twice with (m + n + 1) // 2 and (m + n + 2) // 2 to derive two middle values and take their average.

The use of "inf" ensures that the comparison logic remains correct even when all elements of one array have been accounted for, thus allowing the binary search to proceed correctly with the remaining array.

Data Structures:

• No additional data structures are used, aside from the input arrays and variables to store intermediate values.

Algorithm Patterns:

• Binary Search: The solution utilizes the binary search pattern in a recursive manner to find the kth smallest element in a merged sorted array without actually merging them.
• Divide and Conquer: The problem space is halved in each recursive call, efficiently narrowing down to the median value.
• Recursion: Through the recursive function f(i, j, k), we are capable of diving into smaller subproblems and compositions of the problem.

Overall, the binary search pattern is applied in a unique way that leverages the sorted property of the arrays and the fact that the kth smallest element search can be performed in a log-linear time complexity given these properties.

Example Walkthrough

Let's go through a small example to illustrate the solution approach using two sorted arrays nums1 and nums2.

Consider the arrays nums1 = [1, 3] and nums2 = [2]. The combined array after merging would be [1, 2, 3], where the median is 2 because it is the middle element.

We will not actually merge the arrays. Instead, we will employ the divide and conquer binary search as described.

Step 1: Find the total length and calculate the median position.

The total length of the combined arrays is m + n = 2 + 1 = 3, which is odd. The median position k is (m + n + 1) // 2 = (3 + 1) // 2 = 2.

Step 2: Begin the binary search with the helper function f(i, j, k).

We want to find the 2nd smallest element without merging, so we start by calling f(0, 0, 2). Here i and j are starting indices for nums1 and nums2, and k is 2.

Step 3: Handle the base and recursive cases.

Since k is not 1 and we haven't exceeded array lengths, we find the middle index p for the current k, which is p = k // 2 = 1.

Now, we look at the elements at index p - 1 (since arrays are zero-indexed) in each array. In nums1, it's nums1[0], which is 1, and in nums2, it's nums2[0], which is 2. (We will call these x and y respectively).

Step 4: Eliminate one half of the search space.

Since x < y (1 < 2), we eliminate x and elements to the left of x. Now we call f(i + p, j, k - p), which translates to f(1, 0, 1) because we're moving past the element 1 in nums1.

Step 5: Reaching the base case.

Now k is 1, which means we just need to find the minimum of the current elements nums1[i] and nums2[j]. The array nums1 at index 1 has no more elements, and the array nums2 at index 0 has the element 2.

Since the element in nums1 is out of bounds, we consider it infinity. Therefore, nums2[j] which is 2, is the smaller element.

Step 6: Return the result.

Since we were looking for the 2nd smallest element, 2 is the median, and we return this as the result.

Through this example, we successfully applied the binary search divide and conquer strategy to find the median of two sorted arrays without merging them, fulfilling the required O(log (m+n)) runtime complexity.

Solution Implementation

Time and Space Complexity

The given Python code implements the solution to find the median of two sorted arrays using a divide and conquer approach. Let's analyze the time and space complexity of the code:

Time Complexity:

The time complexity of the function can be understood by considering the primary operation it performs - finding the k-th smallest element in two sorted arrays nums1 and nums2. Each recursive call to the function f(i, j, k) reduces the k by approximately half (k - p, where p = k // 2), and at the same time, it incrementally discards p elements from one of the arrays by advancing the index i or j.

Therefore, the k reduces to 1 after approximately log(k) steps. Since the initial k is derived from the total number of elements in both arrays ((m + n + 1) // 2 or (m + n + 2) // 2), the overall time complexity can be estimated as O(log(m + n)).

Space Complexity:

There is no additional space allocated for storing elements. The space complexity is determined by the depth of the recursion stack. Since we have approximately log(m + n) recursive calls due to the divide and conquer algorithm, and considering each recursive call uses a constant amount of space, the space complexity is O(log(m + n)).

Learn more about how to find time and space complexity quickly using problem constraints.