thesarfo

Reference

Median of Two Sorted Arrays

Finding the median across two sorted arrays by tracking only the two middle positions while merging, without storing the full merged result.

views 0

Special case of Kth Element of Two Sorted Arrays with k = (n+m+1)/2 (and averaging two middle values when the combined length is even). (LeetCode problem)

Brute force: merge fully into a new sorted list, then read off the middle element(s) — O(n+m) time and space.

Better — track only the two middle positions while merging, without storing the whole merged result: walk both arrays with a counter, and whenever the counter hits one of the two candidate middle indices ((n1+n2-1)/2 and (n1+n2)/2), record that value.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int midIndex1 = (n1 + n2 - 1) / 2;
        int midIndex2 = (n1 + n2) / 2;


        int i = 0, j = 0, count = 0;
        int element1 = 0, element2 = 0;


        while (i < n1 && j < n2) {
            int smallerElement;
            if (nums1[i] <= nums2[j]) {
                smallerElement = nums1[i];
                i++;
            } else {
                smallerElement = nums2[j];
                j++;
            }


            if (count == midIndex1) element1 = smallerElement;
            if (count == midIndex2) element2 = smallerElement;
            count++;
        }


        while (i < n1) {
            if (count == midIndex1) element1 = nums1[i];
            if (count == midIndex2) element2 = nums1[i];
            i++; count++;
        }


        while (j < n2) {
            if (count == midIndex1) element1 = nums2[j];
            if (count == midIndex2) element2 = nums2[j];
            j++; count++;
        }


        if ((n1 + n2) % 2 == 0) {
            return (element1 + element2) / 2.0;
        } else {
            return element2;
        }
    }
}

This runs in O(n+m) time with O(1) space — better than the full-merge approach, though the truly optimal solution applies the same partition-based binary search as Kth Element of Two Sorted Arrays to reach O(log(min(n,m))).