Framework Thinking - Neetcode 150 - Median of Two Sorted Arrays
Here is solutions for Median of Two Sorted Arrays.
1. Understand the problem
-
The median is the middle value (or the average of two middles if total length is even).
-
Arrays are already sorted.
-
We need to consider both arrays as if they were merged, but we must do it efficiently => Expect O(log(m + n)).
2. Clarify constraints (4–5 questions)
- What’s the range of m and n?
- 0 ≤ m, n ≤ 10⁵ (some versions allow one array empty)
- Can both arrays be empty?
- No, at least one array must be non-empty.
- Are elements negative or duplicated allowed?
- Yes, both allowed.
- Time complexity requirement?
- Must be O(log(m+n)), so binary search is expected.
- Memory constraints?
- Avoid merging unless naive solution is acceptable.
3. Brainstorm 2 - 3 solutions
3.1. Normal Sort - O((m + n)log(m + n))
-
Concentrate 2 arrays => Sort: O((m + n)log(m + n)).
-
Find 2 middle numbers in the array => Median: O(1)
-
Time: O((m + n)log(m + n)).
-
Space: O(m + n).
3.2. Merge 2 sorted array - O(M + N)
-
Create new array size M + N => Merge to sorted 2 arrays to new array.
-
Find the middle of this array => O(1).
-
Time: O(m + n).
-
Space: O(m + n).
3.3. Find pivot max(left) <= min(right) - O(log(M + N))
-
Find the right pivot to split it so: max(left array) <= min(right array)
-
Key idea:
nums1: [ 1 3 | 5 ]
nums2: [ 2 | 4 ]
Left side combined: [1, 2, 3]
Right side combined: [4, 5]
Total = 5 → median = middle = 3
-
Time: O(log(m + n)).
-
Space: O(m + n).
4. Implement solutions
4.1. Brute force - O((m + n)log(m + n))
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
len1 = len(nums1)
len2 = len(nums2)
merged = nums1 + nums2
merged.sort()
totalLen = len(merged)
if totalLen % 2 == 0:
return (merged[totalLen // 2 - 1] + merged[totalLen // 2]) / 2.0
else:
return merged[totalLen // 2]
-
Time: O((m + n)log(m + n)).
-
Space: O(m + n).
4.2. Two Pointers in 2 sorted array - O(m + n)
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
len1, len2 = len(nums1), len(nums2)
i = j = 0
median1 = median2 = 0
for count in range((len1 + len2) // 2 + 1):
median2 = median1
if i < len1 and j < len2:
if nums1[i] > nums2[j]:
median1 = nums2[j]
j += 1
else:
median1 = nums1[i]
i += 1
elif i < len1:
median1 = nums1[i]
i += 1
else:
median1 = nums2[j]
j += 1
if (len1 + len2) % 2 == 1:
return float(median1)
else:
return (median1 + median2) / 2.0
-
Time: O(m + n).
-
Space: O(m + n).
4.3. Two Heap - O((m + n)log(m + n))
4.4. Binary Search Pivot - O(log(m + n))
nums1: [ ...left1 | right1... ]
nums2: [ ...left2| right2 ... ]
- Note: If left1 > right2 => must make left 1 smaller => move to left of nums1.
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
# Ensure nums1 is the smaller array
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = (total + 1) // 2
left, right = 0, m
while left <= right:
i = (left + right) // 2 # partition in nums1
j = half - i # partition in nums2
left1 = nums1[i - 1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j - 1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
# Check if correct partition
if left1 <= right2 and left2 <= right1:
if total % 2 == 1:
median = max(left1, left2)
else:
median = (max(left1, left2) + min(right1, right2)) / 2
return median
# Move binary search boundaries
elif left1 > right2:
# Move to left and try to make left1 < right2
right = i - 1
else:
left = i + 1
-
Time: O(log(m + n)).
-
Space: O(m + n).
5. Dry run solutions
- Key idea:
nums1: [ 1 3 | 5 ]
nums2: [ 2 | 4 ]
Left side combined: [1, 2, 3]
Right side combined: [4, 5]
Total = 5 → median = middle = 3