How do you solve Median of Two Sorted Arrays on LeetCode?

Median of Two Sorted Arrays (LeetCode #4) can be solved using Brute Force or Optimal Solution (Binary Search). The optimal approach is Optimal Solution (Binary Search) with O(log(min(m, n))) time complexity and O(1) space complexity. Key insight: The key observation is that the median can be found by partitioning the two arrays such that all elements on the left are less than or equal to all elements on the right.

What is the brute force solution for Median of Two Sorted Arrays?

The brute force approach for Median of Two Sorted Arrays is Brute Force, with O(n log n) time complexity and O(n) space complexity. The brute force approach involves merging the two sorted arrays into one sorted array and then finding the median from this merged array. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution (Binary Search) approach improves this to O(log(min(m, n))).

What algorithm or data structure is used to solve Median of Two Sorted Arrays?

Median of Two Sorted Arrays uses the following concepts: Array, Binary Search, Divide and Conquer. The recommended patterns to study are: Binary Search, Array, Two Pointers.

What are the interview tips for Median of Two Sorted Arrays?

When you first see this problem, mention that you recognize it involves finding a median and that you will explore efficient methods to do so. Communicate your approach clearly, explaining how you plan to use binary search and why it’s efficient. Make sure to mention edge cases, such as when one array is empty or when both arrays have the same length.

What are common mistakes when solving Median of Two Sorted Arrays?

Students often forget to handle edge cases where one of the arrays might be empty. Another common mistake is not correctly calculating the partitions and their corresponding max/min values.

Median of Two Sorted Arrays

Hard

ArrayBinary SearchDivide and ConquerBinary SearchArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Binary Search)★
Time	O(n log n)	O(log(min(m, n)))
Space	O(n)	O(1)

💡

Intuition

Time O(log(min(m, n)))Space O(1)

The optimal approach uses binary search to find the correct partition of the two arrays. This allows us to find the median in O(log(min(m, n))) time, which is much faster than merging the arrays.

⚙️

Algorithm

5 steps

1Step 1: Ensure nums1 is the smaller array. If not, swap them.
2Step 2: Initialize binary search on the smaller array.
3Step 3: Calculate partitions for both arrays based on the current binary search index.
4Step 4: Check if the partitions are valid (maxLeft1 <= minRight2 and maxLeft2 <= minRight1).
5Step 5: If valid, calculate the median based on the total length (odd/even). If not, adjust the binary search bounds.

solution.py27 lines

1# Full working Python code with comments
2
3def findMedianSortedArrays(nums1, nums2):
4    if len(nums1) > len(nums2):
5        nums1, nums2 = nums2, nums1
6    x, y = len(nums1), len(nums2)
7    low, high = 0, x
8    while low <= high:
9        partitionX = (low + high) // 2
10        partitionY = (x + y + 1) // 2 - partitionX
11        maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
12        minRightX = float('inf') if partitionX == x else nums1[partitionX]
13        maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
14        minRightY = float('inf') if partitionY == y else nums2[partitionY]
15        if maxLeftX <= minRightY and maxLeftY <= minRightX:
16            if (x + y) % 2 == 0:
17                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0
18            else:
19                return max(maxLeftX, maxLeftY)
20        elif maxLeftX > minRightY:
21            high = partitionX - 1
22        else:
23            low = partitionX + 1
24
25# Example usage
26print(findMedianSortedArrays([1, 3], [2]))  # Output: 2.0
27print(findMedianSortedArrays([1, 2], [3, 4]))  # Output: 2.5

ℹ

Complexity note: The time complexity is O(log(min(m, n))) because we are performing binary search on the smaller array. The space complexity is O(1) since we are using a constant amount of space for variables.

1The key observation is that the median can be found by partitioning the two arrays such that all elements on the left are less than or equal to all elements on the right.
2Another important insight is that we can leverage binary search to efficiently find the correct partition, which reduces the time complexity significantly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.