Median of Two Sorted Arrays

Finding the median value of two sorted arrays.

The problem statement may be found on leetcode.

Analysis of the Problem

The basics of the algorithm are actually very straightforward - it is the edge cases and implementation that made this quite tricky. Given the finite subsets \(\{a_j\}\) and \(\{b_k\}\) of \(\mathbb{N}\) indexed in monotonic order, the algorithm is

1. Take \(j_{start} = max(j)\) and \(j_{stop} = min(j)\), and likewise for \(k_{start}\) and \(k_{stop}\).

2. If \(j_{start} <= j_{stop}\) and \(k_{start} <= k_{stop}\), look at the respective elements for the starts and choose the lesser element - for this element increment the corresponding value of \(j_{start}\) or \(k_{start}\) and record the lesser element \(r\) - then look at the respective elements of the stops and choose the greater and save it as \(l\) - for this element decrement the corresponding value of \(j_{stop}\) or \(k_{stop}\).

   If one array has been expended, just do this for just the remaining array. If both have been expended, stop.

3. Repeat step 2 until \(j_{start} > j_{stop}\) and \(k_{start} > k_{stop}\).

4. Take the mean of \(l\) and \(r\).

Implementation

My initial solution is

class Solution:

    # NOTE: Input arrays should already be sorted.
    def findMedianSortedArrays(
        self,
        nums1: list[int],
        nums2: list[int],
    ) -> float:

        n1, n2 = len(nums1), len(nums2)
        if n1 + n2 == 1:
            if n1 != 0:
                return nums1[0]
            else:
                return nums2[0]

        start_1, start_2 = 0, 0
        stop_1, stop_2 = n1 - 1, n2 - 1
        left, right = None, None

        while True:
            # If both, decide which one to decrement/increment
            if start_1 <= stop_1 and start_2 <= stop_2:
                a, b = nums1[start_1], nums2[start_2]
                if a <= b:
                    left = a
                    start_1 += 1
                else:
                    left = b
                    start_2 += 1

                a, b = nums1[stop_1], nums2[stop_2]
                if a >= b:
                    right = a
                    stop_1 -= 1
                else:
                    right = b
                    stop_2 -= 1
            elif start_1 < stop_1:
                left = nums1[start_1]
                right = nums1[stop_1]

                stop_1 -= 1
                start_1 += 1
            elif start_2 < stop_2:
                left = nums2[start_2]
                right = nums2[stop_2]

                stop_2 -= 1
                start_2 += 1
            elif stop_1 == start_1:
                left = right = nums1[stop_1]
                break
            elif stop_2 == start_2:
                left = right = nums2[stop_2]
                break
            else:
                break

        return (left + right) / 2  # type: ignore[operator]

however it did not rank very well in runtime with a sad \(38\%\) or memory with a horrific \(20\%\). However, my iterated solution simplified the logic and removed the initial step for trivial cases and did shockingly well. It beat \(94\%\) of submissions in runtime and \(99\%\) in memory.

class Solution:

    # NOTE: Input arrays should already be sorted.
    def findMedianSortedArrays(
        self,
        nums1: list[int],
        nums2: list[int],
    ) -> float:

        n1, n2 = len(nums1), len(nums2)
        if n1 + n2 == 1:
            if n1 != 0:
                return nums1[0]
            else:
                return nums2[0]

        start_1, start_2 = 0, 0
        stop_1, stop_2 = n1 - 1, n2 - 1
        left, right = None, None

        while True:
            # If both, decide which one to decrement/increment
            if start_1 <= stop_1 and start_2 <= stop_2:
                a, b = nums1[start_1], nums2[start_2]
                if a <= b:
                    left = a
                    start_1 += 1
                else:
                    left = b
                    start_2 += 1

                a, b = nums1[stop_1], nums2[stop_2]
                if a >= b:
                    right = a
                    stop_1 -= 1
                else:
                    right = b
                    stop_2 -= 1
            elif start_1 < stop_1:
                left = nums1[start_1]
                right = nums1[stop_1]

                stop_1 -= 1
                start_1 += 1
            elif start_2 < stop_2:
                left = nums2[start_2]
                right = nums2[stop_2]

                stop_2 -= 1
                start_2 += 1
            elif stop_1 == start_1:
                left = right = nums1[stop_1]
                break
            elif stop_2 == start_2:
                left = right = nums2[stop_2]
                break
            else:
                break

        return (left + right) / 2  # type: ignore[operator]