- If one of the array is small enough, i.e. less than 5 numbers, then we can build a small array and sort and find the median.
- If the two arrays are large enough, it's not possible to do it that way. We need to shrink the two arrays to #1, then we can build the small array and find the median.

So the question is how to shrink the arrays safely without dropping the critical numbers. For example:

- array1={1,3,5,6,8};
- array2={-5,-2,2,3,4,5,6,7,8,9, 10, 11};

Firstly, pick up the two middle numbers. Here, they are 5 and 6. So we know any numbers on the right of 6 in array2 could not contribute to the median value. And any numbers on the left of 5 in array1 could not neither. So the problem becomes find median in:

- array1={5,6,8};
- array2={2,3,4,5,6,7,8,9};

Since the size of array1 is less than 4, it's a trivial problem. We can still optimize it a little bit. We can drop the number heading/trailing of array2 since they do not contribute to the median. This way, we can make sure the memory allocated is O(1).

```
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums1.empty() && nums2.empty()) return 0;
if(nums1.size()>nums2.size()){
swap(nums1, nums2);
}
return findMedian(nums1, 0, nums1.size(), nums2, 0, nums2.size());
}
double findMedian(vector<int>& nums1, int left1, int right1, vector<int>& nums2, int left2, int right2){
while(true){
if(right1-left1<=4){
int size1=right1-left1;
int size2=right2-left2;
int diff=max(0,(size2-size1)/2-1);
vector<int> v(nums2.begin()+left2+diff, nums2.begin()+right2-diff);
for(int i=left1; i<right1; ++i){
v.push_back(nums1[i]);
}
sort(v.begin(), v.end());
int size=v.size();
return (v[size/2]+v[(size-1)/2])/2.0;
}
else{
int mid1=(left1+right1)/2;
int mid2=(left2+right2)/2;
if(nums1[mid1]<nums2[mid2]){//remove left of nums1 and right of nums2
int diff=min(mid1-left1, right2-mid2-1);
left1+=diff;
right2-=diff;
}
else{
int diff=min(right1-mid1-1, mid2-left2);
right1-=diff;
left2+=diff;
}
}
}
return 0;
}};
```