<p>Given two sorted arrays <code>nums1</code> and <code>nums2</code> of size <code>m</code> and <code>n</code> respectively, return <strong>the median</strong> of the two sorted arrays.</p>

<p>The overall run time complexity should be <code>O(log (m+n))</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>nums1.length == m</code></li>
	<li><code>nums2.length == n</code></li>
	<li><code>0 &lt;= m &lt;= 1000</code></li>
	<li><code>0 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= m + n &lt;= 2000</code></li>
	<li><code>-10<sup>6</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # neetcode soln
        a, b = nums1, nums2
        if len(a) > len(b):
            a, b = b, a
        
        total = len(a) + len(b)
        half = total // 2
        l, r = 0, len(a)-1

        while True:
            # compute a and b mids
            aMid = (l + r) // 2 # a's pointer
            bMid = half - (aMid + 2) # b's pointer

            # find left and right partitions of a and b
            aLeft = a[aMid] if aMid >= 0 else float('-inf')
            bLeft = b[bMid] if bMid >= 0 else float('-inf')
            aRight = a[aMid + 1] if (aMid + 1) < len(a) else float('inf')
            bRight = b[bMid + 1] if (bMid + 1) < len(b) else float('inf')

            # return median if partitions are valid else change l and r to adjust the partitions 
            if aLeft <= bRight and bLeft <= aRight:
                if total % 2:
                    return min(aRight, bRight) 
                else:
                    return (max(aLeft, bLeft) + min(aRight, bRight)) / 2
            elif bLeft > aRight:
                l = aMid + 1
            else:
                r = aMid - 1
        

        

        # my soln - time O(m+n), space O(m+n)
        # l, r = 0, 0
        # res = []

        # while l < len(nums1) and r < len(nums2):
        #     if nums1[l] < nums2[r]:
        #         res.append(nums1[l])
        #         l += 1
        #     else:
        #         res.append(nums2[r])
        #         r += 1

        # res += nums1[l:] if l < len(nums1) else nums2[r:]

        # if len(res) % 2 == 0:
        #     return (res[len(res)//2] + res[(len(res)//2)-1]) / 2
        # else:
        #     return res[len(res)//2]


        # my soln - time O((m+n)log(m+n)), space O(m+n)
        # nums1.extend(nums2)
        # nums1.sort()
        # n = len(nums1)
        # if n % 2 == 0:
        #     return (nums1[n//2] + nums1[(n//2)-1])/2
        # else:
        #     return nums1[n//2]

                    


         # my soln - time O(m+n), space O(1)- Failed attempt
        # Check if one of the arrays is empty
        # if not nums1:
        #     # Calculate median of nums2
        #     n = len(nums2)
        #     if n % 2 == 0:
        #         return (nums2[n // 2 - 1] + nums2[n // 2]) / 2
        #     else:
        #         return nums2[n // 2]
        # if not nums2:
        #     # Calculate median of nums1
        #     m = len(nums1)
        #     if m % 2 == 0:
        #         return (nums1[m // 2 - 1] + nums1[m // 2]) / 2
        #     else:
        #         return nums1[m // 2]


        # length = len(nums1) + len(nums2)
        # mid = 0
        # if length % 2 == 0:
        #     mid = (length // 2) - 1
        # else:
        #     mid = (length // 2)

        # l = r = 0
        # while mid != 0 and l < len(nums1) and r < len(nums2):
        #     if nums1[l] < nums2[r]:
        #         l += 1
        #     else:
        #         r += 1
        #     mid -= 1
        
        # while mid != 0:
        #     if l < len(nums1):
        #         mid -= 1
        #         l += 1
        #     elif r < len(nums2):
        #         mid -= 1
        #         r += 1

        # if length % 2 == 0:
        #     return (nums1[l] + nums2[r]) / 2  
        # else:
        #     return min(nums1[l], nums2[r])
                        

                    
                
        
 
        

16400