# 4. Median of Two Sorted Arrays

## Problem Statement

<br>

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))`.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums1 = [1,3], nums2 = [2]
</strong><strong>Output: 2.00000
</strong><strong>Explanation: merged array = [1,2,3] and median is 2.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums1 = [1,2], nums2 = [3,4]
</strong><strong>Output: 2.50000
</strong><strong>Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
</strong></code></pre>

&#x20;

**Constraints:**

* `nums1.length == m`
* `nums2.length == n`
* `0 <= m <= 1000`
* `0 <= n <= 1000`
* `1 <= m + n <= 2000`
* `-106 <= nums1[i], nums2[i] <= 106`

## Intuition

```
```

### Links

<https://leetcode.com/problems/median-of-two-sorted-arrays/description/>

### Video Links

<https://www.youtube.com/watch?v=C2rRzz-JDk8&ab_channel=takeUforward>

### Approach 1:

```
Brute:
NlogN time and 1 Space

Directly Inserted one array in other and used sort
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        nums1.insert(nums1.end(), nums2.begin(), nums2.end());
        sort(nums1.begin(), nums1.end());

        int n = nums1.size();
        if(n == 0)  return 0;
        int idx = n/2;
        if(n%2 == 0)
            return (nums1[idx]+nums1[idx-1])/2.0;
        
        return nums1[idx];
    }
};
```

{% endcode %}

### Approach 2:

```
Merge Algorithm
m+n time and m+n space

Merged two sorted using pointers in other array
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> arr;
        int i=0, j=0;

        while(i<nums1.size() and j<nums2.size()){
            if(nums1[i] < nums2[j])
                arr.push_back(nums1[i++]);
            else
                arr.push_back(nums2[j++]);
        }

        while(i<nums1.size())
            arr.push_back(nums1[i++]);

        while(j<nums2.size())
            arr.push_back(nums2[j++]);

        int index = arr.size()/2;
        if(arr.size() % 2 == 0)
            return (arr[index] + arr[index-1]) / 2.0;

        return arr[index];
    }
};
```

{% endcode %}

### Approach 3:

```
Merge Algorithm optimised
m+n time and 1 space

Maintained variables to keep track of index
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int i=0, j=0;
        int count = 0;
        int idx1 = (m+n)/2;
        int idx2 = idx1-1;
        int el_1, el_2;

        while(i<nums1.size() and j<nums2.size()){
            if(nums1[i] < nums2[j]){
                if(count == idx1)   el_1 = nums1[i];
                if(count == idx2)   el_2 = nums1[i];
                count++;
                i++;
            }
            else{
                if(count == idx1)   el_1 = nums2[j];
                if(count == idx2)   el_2 = nums2[j];
                count++;
                j++;
            }
        }

        while(i<nums1.size()){
            if(count == idx1)   el_1 = nums1[i];
            if(count == idx2)   el_2 = nums1[i];
            count++;
            i++;
        }

        while(j<nums2.size()){
            if(count == idx1)   el_1 = nums2[j];
            if(count == idx2)   el_2 = nums2[j];
            count++;
            j++;
        }
        cout<<el_1<<" "<<el_2<<endl;
        if((m+n) % 2 == 0)
            return (el_1 + (double)el_2) / 2.0;

        return el_1;
    }
};
```

{% endcode %}

### Approach 4:

```
Optimal-> Binary Search
log(min(n,m))

Basically
1 2 3 4 5 6 7 8 9
Some elements come from arr1, other from arr2

symmetry Choose half elements

Now Try to take some elements from arr1 and some from arr2, for this half

arr1 = 1 3 4 7 10 12
arr2 = 2 3 6 15

To choose 5 elements for left half

1 3 4l1 | r1 7 10 12
2 3l2   | r2 6 15

Compare  l1 with r2, l2 with r1
To shrink or expand the BS on taking more or less from the array

,

To find for odd
m+n+1/2 used
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m>n) 
            return findMedianSortedArrays(nums2,nums1);

        int low=0, high=m;
        int left = (m+n+1)/2;
        while(low<=high){
            int mid1 = low+(high-low)/2;
            int mid2 = left-mid1;

            int l1=INT_MIN, l2=INT_MIN;
            int r1=INT_MAX, r2=INT_MAX;

            if(mid1 < m)    r1=nums1[mid1];
            if(mid2 < n)    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){
                if( (m+n) % 2 == 1)
                    return max(l1,l2);

                return (max(l1,l2) + min(r1,r2)) / 2.0;
            } 
            else if(l1>r2)
                high = mid1-1;
            else
                low = mid1+1;
        }

        return 0;
    }
};
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/4.-median-of-two-sorted-arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.