Challenges

LogoFind Peak Element - LeetCodeLeetCode
LogoLoading...LeetCode

For this issue, follow first challenge on this thread https://app.gitbook.com/o/h0Ny2Dx4tM7wlLiHltUk/s/wNXdoUkfmcozr29fRrfb/~/changes/453/algorithm/more/pigeonhole-principle/challenge

def findMedianSortedArrays(nums1, nums2):
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    
    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        
        if i < m and nums2[j-1] > nums1[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect
            if i == 0: max_of_left = nums2[j-1]
            elif j == 0: max_of_left = nums1[i-1]
            else: max_of_left = max(nums1[i-1], nums2[j-1])
            
            if (m + n) % 2 == 1:
                return max_of_left
            
            if i == m: min_of_right = nums2[j]
            elif j == n: min_of_right = nums1[i]
            else: min_of_right = min(nums1[i], nums2[j])
            
            return (max_of_left + min_of_right) / 2.0
def findMedianSortedArrays(nums1, nums2):

  • Line 1: Defines a function named findMedianSortedArrays that takes two input parameters: nums1 and nums2, which represent two sorted arrays.

    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

  • Lines 2-4: These lines check if nums1 is larger than nums2 in length. If so, the arrays are swapped. This ensures that we perform the binary search on the smaller array, reducing the overall time complexity.

    m, n = len(nums1), len(nums2)
    imin, imax, half_len = 0, m, (m + n + 1) // 2

  • Line 5: m and n store the lengths of nums1 and nums2, respectively.

  • Line 6: imin and imax are initialized as the starting and ending indices for binary search on nums1. half_len is the half of the combined length of both arrays, used to calculate the partition points.

    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i

  • Line 7: A while loop is used for binary search, which continues as long as imin is less than or equal to imax.

  • Line 8: i is the partition index for nums1, calculated as the midpoint of imin and imax.

  • Line 9: j is the corresponding partition index for nums2, ensuring that the total number of elements on both sides of the partition is equal or nearly equal.

    if i < m and nums2[j-1] > nums1[i]:
            # i is too small, must increase it
            imin = i + 1

  • Lines 10-12: These lines check if the partition in nums1 is too far to the left, i.e., the element just to the left of the partition in nums2 is greater than the element just to the right of the partition in nums1. In this case, imin is moved to the right (i + 1) to increase i in the next iteration.

    elif i > 0 and nums1[i-1] > nums2[j]:
            # i is too big, must decrease it
            imax = i - 1

  • Lines 13-15: These lines check if the partition in nums1 is too far to the right, i.e., the element just to the left of the partition in nums1 is greater than the element just to the right of the partition in nums2. In this case, imax is moved to the left (i - 1) to decrease i in the next iteration.

    else:
            # i is perfect
            if i == 0: max_of_left = nums2[j-1]
            elif j == 0: max_of_left = nums1[i-1]
            else: max_of_left = max(nums1[i-1], nums2[j-1])

  • Line 16: If neither of the above conditions are true, it means the partition i is correct, and the elements on both sides of the partition satisfy the median condition.

  • Lines 17-19: These lines handle the edge cases where i or j is at the boundary of an array:

    • If i == 0, it means all elements on the left side of the partition are from nums2, so max_of_left is set to nums2[j-1].

    • If j == 0, all elements on the left side are from nums1, so max_of_left is set to nums1[i-1].

    • Otherwise, max_of_left is the larger of the two elements on the left side of the partition from both arrays.

           if (m + n) % 2 == 1:
                return max_of_left

  • Lines 20-21: If the total number of elements (m + n) is odd, the median is simply max_of_left, because the middle element is on the left side of the partition.

       if i == m: min_of_right = nums2[j]
            elif j == n: min_of_right = nums1[i]
            else: min_of_right = min(nums1[i], nums2[j])

  • Lines 22-24: If the total number of elements (m + n) is even, the median is the average of the largest element on the left side (max_of_left) and the smallest element on the right side (min_of_right):

    • If i == m, all elements on the right side are from nums2, so min_of_right is nums2[j].

    • If j == n, all elements on the right side are from nums1, so min_of_right is nums1[i].

    • Otherwise, min_of_right is the smaller of the two elements on the right side of the partition from both arrays.

    return (max_of_left + min_of_right) / 2.0

  • Line 25: Finally, for the even case, return the average of max_of_left and min_of_right as the median.

Summary:

  • The function uses binary search to partition the smaller array, adjusting the partition until the correct median is found.

  • It handles both odd and even total element cases.

  • The time complexity of this approach is O(log⁡(min(m,n)))O(\log(\text{min}(m, n)))O(log(min(m,n))), making it efficient for large input sizes.

PreviousBinary SearchNextLinear Search

Last updated