# Median of two sorted arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return **the median** of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

```
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
n1 = len(nums1)
n2 = len(nums2)
# Ensure nums1 is the smaller array for simplicity
if n1 > n2:
return self.findMedianSortedArrays(nums2, nums1)
n = n1 + n2
left = (n1 + n2 + 1) // 2 # Calculate the left partition size
low = 0
high = n1
while low <= high:
mid1 = (low + high) // 2 # Calculate mid index for nums1
mid2 = left - mid1 # Calculate mid index for nums2
l1 = float('-inf')
l2 = float('-inf')
r1 = float('inf')
r2 = float('inf')
# Determine values of l1, l2, r1, and r2
if mid1 < n1:
r1 = nums1[mid1]
if mid2 < n2:
r2 = nums2[mid2]
if mid1 - 1 >= 0:
l1 = nums1[mid1 - 1]
if mid2 - 1 >= 0:
l2 = nums2[mid2 - 1]
if l1 <= r2 and l2 <= r1:
# The partition is correct, we found the median
if n % 2 == 1:
return max(l1, l2)
else:
return (max(l1, l2) + min(r1, r2)) / 2.0
elif l1 > r2:
# Move towards the left side of nums1
high = mid1 - 1
else:
# Move towards the right side of nums1
low = mid1 + 1
return 0 # If the code reaches here, the input arrays were not sorted.
```

## Related Problems

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given a **non-empty** array of integers nums, every element appears *twice* except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.