Median Of Two Sorted Arrays

                                            
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int x = nums1.size();
        int y = nums2.size();
        int low = 0, high = x;
        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;
            
            int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
            int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
            
            int minX = (partitionX == x) ? INT_MAX : nums1[partitionX];
            int minY = (partitionY == y) ? INT_MAX : nums2[partitionY];
            
            if (maxX <= minY && maxY <= minX) {
                if ((x + y) % 2 == 0) {
                    return (double)(max(maxX, maxY) + min(minX, minY)) / 2;
                } else {
                    return (double)max(maxX, maxY);
                }
            } else if (maxX > minY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }
        
        throw invalid_argument("Input arrays are not sorted or of unacceptable size.");
    }
};

                                            
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int totalLeft = (m + n + 1) / 2;
        
        int left = 0;
        int right = m;
        
        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;

            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }
        
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        
        if (((m + n) % 2) == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax) * 1.0;
        } else {
            return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
        }
    }
}

                                            
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2
        
        if len(B) < len(A):
            A, B = B, A
        
        l, r = 0, len(A) - 1
        while True:
            i = (l + r) // 2 
            j = half - i - 2
            
            Aleft = A[i] if i >= 0 else float('-inf')
            Aright = A[i + 1] if (i + 1) < len(A) else float('inf')
            Bleft = B[j] if j >= 0 else float('-inf')
            Bright = B[j + 1] if (j + 1) < len(B) else float('inf')
            
            if Aleft <= Bright and Bleft <= Aright:
                if total % 2:
                    return min(Aright, Bright)
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
            
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1

                                            
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int total = nums1Size + nums2Size;
    int half = total / 2;
    if (nums1Size > nums2Size) {
        int* temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        int tmpSize = nums1Size;
        nums1Size = nums2Size;
        nums2Size = tmpSize;
    }
    
    int minIndex = 0, maxIndex = nums1Size, i, j;
    while (minIndex <= maxIndex) {
        i = (minIndex + maxIndex) / 2;
        j = half - i;
        
        if (i < maxIndex && nums2[j - 1] > nums1[i]) {
            minIndex = i + 1;
        } else if (i > minIndex && nums1[i - 1] > nums2[j]) {
            maxIndex = i - 1;
        } else {
            int minRight;
            if (i == nums1Size) {
                minRight = nums2[j];
            } else if (j == nums2Size) {
                minRight = nums1[i];
            } else {
                minRight = nums2[j] < nums1[i] ? nums2[j] : nums1[i];
            }
            
            if (total % 2) return minRight;
            
            int maxLeft;
            if (i == 0) {
                maxLeft = nums2[j - 1];
            } else if (j == 0) {
                maxLeft = nums1[i - 1];
            } else {
                maxLeft = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
            }
            
            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0;
}

                                            
public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.Length > nums2.Length) {
            return FindMedianSortedArrays(nums2, nums1);
        }

        int x = nums1.Length;
        int y = nums2.Length;
        int low = 0, high = x;
        
        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            int maxLeftX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? int.MaxValue : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? int.MaxValue : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if((x + y) % 2 == 0) {
                    return ((double)Math.Max(maxLeftX, maxLeftY) + Math.Min(minRightX, minRightY)) / 2;
                } else {
                    return (double)Math.Max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }

        throw new ArgumentException("Input arrays are not correct.");
    }
}

                                            
var findMedianSortedArrays = function(nums1, nums2) {
    const totalLength = nums1.length + nums2.length;
    let index1 = 0, index2 = 0;
    let current = 0, last = 0;

    for (let i = 0; i <= Math.floor(totalLength / 2); i++) {
        last = current;
        if (index1 < nums1.length && (index2 >= nums2.length || nums1[index1] < nums2[index2])) {
            current = nums1[index1++];
        } else {
            current = nums2[index2++];
        }
    }

    if (totalLength % 2 === 0) {
        return (last + current) / 2.0;
    } else {
        return current;
    }
};

                                            
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    const m = nums2.length;
    if (n > m) return findMedianSortedArrays(nums2, nums1); // Ensure that nums1 is the smaller array

    let low = 0, high = n;
    const combinedLength = n + m;
    while (low <= high) {
        const partitionX = (low + high) >> 1;
        const partitionY = ((n + m + 1) >> 1) - partitionX;

        const maxX = partitionX === 0 ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
        const maxY = partitionY === 0 ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
        const minX = partitionX === n ? Number.POSITIVE_INFINITY : nums1[partitionX];
        const minY = partitionY === m ? Number.POSITIVE_INFINITY : nums2[partitionY];

        if (maxX <= minY && maxY <= minX) {
            if ((combinedLength & 1) === 0) {
                return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;
            } else {
                return Math.max(maxX, maxY);
            }
        } else if (maxX > minY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    return 0;
}

                                            
class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2) {
        if (count($nums1) > count($nums2)) {
            return $this->findMedianSortedArrays($nums2, $nums1);
        }
        
        $x = count($nums1);
        $y = count($nums2);
        
        $low = 0;
        $high = $x;
        
        while ($low <= $high) {
            $partitionX = ($low + $high) >> 1;
            $partitionY = (($x + $y + 1) >> 1) - $partitionX;
            
            $maxLeftX = ($partitionX == 0) ? PHP_INT_MIN : $nums1[$partitionX - 1];
            $minRightX = ($partitionX == $x) ? PHP_INT_MAX : $nums1[$partitionX];
            
            $maxLeftY = ($partitionY == 0) ? PHP_INT_MIN : $nums2[$partitionY - 1];
            $minRightY = ($partitionY == $y) ? PHP_INT_MAX : $nums2[$partitionY];
            
            if ($maxLeftX <= $minRightY && $maxLeftY <= $minRightX) {
                if (($x + $y) % 2 == 0) {
                    return (max($maxLeftX, $maxLeftY) + min($minRightX, $minRightY)) / 2.0;
                } else {
                    return max($maxLeftX, $maxLeftY);
                }
            } elseif ($maxLeftX > $minRightY) {
                $high = $partitionX - 1;
            } else {
                $low = $partitionX + 1;
            }
        }
        return -1;
    }
}

                                            
class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        let total = nums1.count + nums2.count
        let half = total / 2
        
        var a = nums1, b = nums2
        if nums1.count > nums2.count {
            a = nums2
            b = nums1
        }
        
        var l = 0, r = a.count
        while l <= r {
            let i = l + (r - l) / 2
            let j = half - i
            
            let aLeft = (i > 0) ? a[i - 1] : Int.min
            let aRight = (i < a.count) ? a[i] : Int.max
            let bLeft = (j > 0) ? b[j - 1] : Int.min
            let bRight = (j < b.count) ? b[j] : Int.max
            
            if aLeft <= bRight && bLeft <= aRight {
                if total % 2 == 0 {
                    return Double(max(aLeft, bLeft) + min(aRight, bRight)) / 2.0
                } else {
                    return Double(min(aRight, bRight))
                }
            } else if aLeft > bRight {
                r = i - 1
            } else {
                l = i + 1
            }
        }
        
        return 0.0
    }
}

                                            
class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        if (nums1.size > nums2.size) return findMedianSortedArrays(nums2, nums1)

        val x = nums1.size
        val y = nums2.size
        var low = 0
        var high = x
        while (low <= high) {
            val partitionX = (low + high) / 2
            val partitionY = (x + y + 1) / 2 - partitionX

            val maxLeftX = if (partitionX == 0) Int.MIN_VALUE else nums1[partitionX - 1]
            val minRightX = if (partitionX == x) Int.MAX_VALUE else nums1[partitionX]

            val maxLeftY = if (partitionY == 0) Int.MIN_VALUE else nums2[partitionY - 1]
            val minRightY = if (partitionY == y) Int.MAX_VALUE else nums2[partitionY]

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                return if ((x + y) % 2 == 0) {
                    (maxOf(maxLeftX, maxLeftY).toDouble() + minOf(minRightX, minRightY)) / 2.0
                } else {
                    maxOf(maxLeftX, maxLeftY).toDouble()
                }
            } else if (maxLeftX > minRightY) {
                high = partitionX - 1
            } else {
                low = partitionX + 1
            }
        }

        throw IllegalArgumentException()
    }
}

                                            
class Solution {
  double findMedianSortedArrays(List<int> nums1, List<int> nums2) {
    int total = nums1.length + nums2.length;
    List<int> merged = List.filled(total, 0);
    int i = 0, j = 0, k = 0;

    // Merge two arrays
    while (i < nums1.length && j < nums2.length) {
      if (nums1[i] < nums2[j]) {
        merged[k++] = nums1[i++];
      } else {
        merged[k++] = nums2[j++];
      }
    }
    while (i < nums1.length) {
      merged[k++] = nums1[i++];
    }
    while (j < nums2.length) {
      merged[k++] = nums2[j++];
    }

    // Find median
    if (total % 2 == 1) {
      return merged[total ~/ 2].toDouble();
    }
    int mid1 = total ~/ 2 - 1;
    int mid2 = total ~/ 2;
    return (merged[mid1] + merged[mid2]) / 2.0;
  }
}

                                            
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1
    }

    x, y := len(nums1), len(nums2)
    low, high := 0, x

    for low <= high {
        partitionX := (low + high) / 2
        partitionY := (x + y + 1) / 2 - partitionX

        maxX := -1 << 31
        if partitionX != 0 {
            maxX = nums1[partitionX-1]
        }
        maxY := -1 << 31
        if partitionY != 0 {
            maxY = nums2[partitionY-1]
        }

        minX := 1<<31 - 1
        if partitionX != x {
            minX = nums1[partitionX]
        }
        minY := 1<<31 - 1
        if partitionY != y {
            minY = nums2[partitionY]
        }

        if maxX <= minY && maxY <= minX {
            if (x+y)%2 == 0 {
                return float64(max(maxX, maxY)+min(minX, minY)) / 2.0
            } else {
                return float64(max(maxX, maxY))
            }
        } else if maxX > minY {
            high = partitionX - 1
        } else {
            low = partitionX + 1
        }
    }

    return -1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
def find_median_sorted_arrays(nums1, nums2)
  merged = (nums1 + nums2).sort
  len = merged.length
  if len.even?
    (merged[len / 2 - 1] + merged[len / 2]) / 2.0
  else
    merged[len / 2]
  end
end

                                            
object Solution {
    def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
        val totalLength = nums1.length + nums2.length
        val middleIndex = totalLength / 2
        
        var i = 0
        var j = 0
        var current = 0
        var prev = 0

        while (i + j <= middleIndex) {
            prev = current
            if (i < nums1.length && (j >= nums2.length || nums1(i) < nums2(j))) {
                current = nums1(i)
                i += 1
            } else {
                current = nums2(j)
                j += 1
            }
        }

        if (totalLength % 2 == 0) (prev + current) / 2.0 else current.toDouble
    }
}

                                            
impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let (mut i, mut j, m, n) = (0, 0, nums1.len(), nums2.len());
        let total = m + n;
        let half = total / 2;
        let mut a = 0;
        let mut b = 0;

        while i + j <= half {
            if i < m && (j >= n || nums1[i] < nums2[j]) {
                a = b;
                b = nums1[i];
                i += 1;
            } else {
                a = b;
                b = nums2[j];
                j += 1;
            }
        }

        if total % 2 == 0 {
            (a as f64 + b as f64) / 2.0
        } else {
            b as f64
        }
    }
}

                                            
(define/contract (find-median-sorted-arrays nums1 nums2)
  (-> (listof exact-integer?) (listof exact-integer?) flonum?)
  (define (merge-lists l1 l2)
    (if (null? l1) l2
        (if (null? l2) l1
            (if (< (car l1) (car l2))
                (cons (car l1) (merge-lists (cdr l1) l2))
                (cons (car l2) (merge-lists l1 (cdr l2)))))))
  (define merged-list (merge-lists nums1 nums2))
  (define len (length merged-list))
  (if (odd? len)
      (exact->inexact (list-ref merged-list (quotient len 2)))
      (/ (+
          (exact->inexact (list-ref merged-list (quotient len 2)))
          (exact->inexact (list-ref merged-list (- (quotient len 2) 1))))
         2)))

                                            
-spec find_median_sorted_arrays([integer()], [integer()]) -> float().
find_median_sorted_arrays(Nums1, Nums2) ->
    Combined = lists:sort(Nums1 ++ Nums2),
    Len = length(Combined),
    Mid = Len div 2,
    if
        Len rem 2 == 1 ->
            lists:nth(Mid + 1, Combined);
        true ->
            (lists:nth(Mid, Combined) + lists:nth(Mid + 1, Combined)) / 2
    end.

                                            
defmodule Solution do
  @spec find_median_sorted_arrays(nums1 :: [integer], nums2 :: [integer]) :: float
  def find_median_sorted_arrays(nums1, nums2) do
    merged = Enum.sort(nums1 ++ nums2)
    
    length = length(merged)
    mid = div(length, 2)

    if rem(length, 2) == 0 do
      (Enum.at(merged, mid - 1) + Enum.at(merged, mid)) / 2.0
    else
      Enum.at(merged, mid)
    end
  end
end

To solve this coding challenge, we need to find the median of two sorted arrays with a combined complexity of O(log(m+n)). This is a nuanced problem that can be tackled using a binary search algorithm.

Explanation

Given two sorted arrays

nums1

and

nums2

, both of different sizes or even potentially empty, our task is to find the median of the combined sorted array. The detailed solution involves using binary search to partition the two arrays such that the median can be easily deduced from the partitioned subsets. Here’s a detailed explanation of each step involved: Key Steps :

Determine Total Length and Half Length :

Calculate the total length of the combined arrays.
Determine half of this total length. This is useful in the binary search as it helps in partitioning the arrays effectively.

Ensure the Smaller Array is First :

Always conduct binary searches on the smaller array. This ensures efficiency, as binary search on a larger array can become more complex.

Binary Search Partitioning :

Use binary search to horizontally partition the smaller and larger arrays.
We need to find the correct partition such that all elements in the left partition are less than or equal to all elements in the right partition.

Edge Cases Handling :

Treat edge cases where partitions may extend beyond the array bounds by using
-infinity

and
+infinity

to simplify comparisons.

Calculate Median Based on Partition :

If the combined length is odd, the median is the minimum of the right-side values.
If even, the median is the average of the maximum of left-side values and the minimum of right-side values.

Let’s go through the pseudocode with detailed comments:

Pseudocode with Comments

                                            
function findMedianSortedArrays(nums1, nums2):
# Ensure nums1 is the smaller array to maintain efficiency
if length(nums1) > length(nums2):
return findMedianSortedArrays(nums2, nums1)

# Array A is the smaller array, Array B is the larger one
A, B = nums1, nums2
total_length = length(A) + length(B)
half_length = total_length // 2

# Initialize binary search bounds
left = 0
right = length(A) - 1

while true:
# Find mid-point of A for the partition
i = (left + right) // 2
# Calculate the corresponding partition index in B
j = half_length - i - 2

# Identify values around the partition in both arrays
Aleft = A[i] if i >= 0 else -infinity
Aright = A[i + 1] if (i + 1) < length(A) else infinity
Bleft = B[j] if j >= 0 else -infinity
Bright = B[j + 1] if (j + 1) < length(B) else infinity

# Correct partition found
if Aleft <= Bright and Bleft <= Aright:
# If the total length is odd, the median is the minimum right element
if total_length % 2 == 1:
return min(Aright, Bright)
# If even, the median is the average of the max left and min right values
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0

# Adjust search range:
# If left part of A is too large, narrow search to the left
elif Aleft > Bright:
right = i - 1
# Otherwise, narrow search to the right
else:
left = i + 1

Detailed Steps in Pseudocode:

Check if
nums1

is larger than
nums2

. If so, swap them to ensure binary search happens on the smaller array.
Determine the total length of the combined arrays and the half length.
Initialize binary search boundary variables,
left

and
right

.
Enter a infinite loop, which will iteratively narrow down the search range:

Calculate partition indices
i

and
j

for arrays
A

and
B

respectively.
Determine the boundary values around the partition.
If valid partitioning condition met (i.e., elements in the left from both arrays are less than elements on the right), calculate the median based on the total length being odd or even.
Adjust the search range based on the comparison results to either shrink to the left or right half of the smaller array.

Thus, the pseudocode provides a structured approach to efficiently solve the problem with the desired time complexity.