Skip to content

The Merged Median

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 2 (Click for link to problem statements)

The Merged Median

Two already-sorted rankings are given as nums1 and nums2. You need the median of all the values combined, and the intended solution runs in logarithmic time rather than merging everything.

Return the median of the two sorted arrays as a float.

def find_median_sorted_arrays(nums1, nums2):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 35-45 mins
  • 🛠️ Topics: Binary Search, Divide and Conquer, Arrays

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: What is the median of a combined collection of values?

    • A: If the combined length is odd, it is the middle value of the merged sorted order. If the combined length is even, it is the average of the two middle values, returned as a float.

  • Q: Can we just merge the two arrays and pick the middle?

    • A: That works but takes O(m + n) time. The problem asks for a logarithmic solution, so we should binary search instead of merging.

  • Q: Can one of the arrays be empty?

    • A: Yes. As long as the combined collection has at least one value, the median is just the median of the non-empty array.
HAPPY CASE
Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: The merged order is [1, 2, 3]. The combined length is odd, so the median is the middle value, 2.0.

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Explanation: The merged order is [1, 2, 3, 4]. The combined length is even, so the median is the average of the two middle values, (2 + 3) / 2 = 2.5.

EDGE CASE
Input: nums1 = [], nums2 = [2, 4]
Output: 3.0
Explanation: One ranking is empty, so the median comes entirely from the other array: (2 + 4) / 2 = 3.0.

Input: nums1 = [7, 8, 9], nums2 = [1, 2, 3, 4]
Output: 4.0
Explanation: The rankings do not overlap at all. The merged order is [1, 2, 3, 4, 7, 8, 9], and the middle value is 4.0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Searching in Sorted Arrays, we can consider the following approaches:

  • Binary Search on a Partition: Instead of searching for a value, binary search for the cut point that splits both arrays into a combined left half and right half of the correct sizes. This is the key pattern that achieves the required logarithmic time.
  • Divide and Conquer: Each comparison lets us discard half of the remaining cut positions, just like classic binary search discards half of the remaining values.
  • Two Pointers / Merge: Merging until the middle is a valid baseline, but its O(m + n) time does not meet the logarithmic requirement.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Binary search over the shorter array for a partition. Take i elements from nums1 and j = half - i elements from nums2 so that the combined left side holds half of all values. The partition is correct when every value on the left side is less than or equal to every value on the right side, which only requires comparing the four values adjacent to the cut: left1 <= right2 and left2 <= right1. Once the correct cut is found, the median is read directly off those boundary values — no merging needed.

1) If nums1 is longer than nums2, swap them so we binary search the shorter array.
2) Let m = len(nums1), n = len(nums2), and half = (m + n + 1) // 2 (size of the combined left side).
3) Binary search i in the range [0, m]:
   a) Set j = half - i.
   b) Let left1/right1 be the values just before/after the cut in nums1 (use -infinity/+infinity when the cut is at an end).
   c) Let left2/right2 be the same for nums2.
   d) If left1 <= right2 and left2 <= right1, the partition is correct:
      - If (m + n) is odd, return max(left1, left2) as a float.
      - Otherwise, return (max(left1, left2) + min(right1, right2)) / 2.
   e) If left1 > right2, we took too many from nums1: search the lower half (high = i - 1).
   f) Otherwise, we took too few from nums1: search the upper half (low = i + 1).

⚠️ Common Mistakes

  • Binary searching the longer array, which lets j = half - i go negative or past the end of the other array.
  • Forgetting the sentinel values (-infinity / +infinity) when the cut sits at index 0 or at the very end of an array, causing index-out-of-range errors.
  • Mixing up the odd and even cases: the odd case uses only max(left1, left2), while the even case also needs min(right1, right2).
  • Returning an integer instead of a float when the combined length is odd.

4: I-mplement

Implement the code to solve the algorithm.

def find_median_sorted_arrays(nums1, nums2):
    # Always binary search over the shorter array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2  # size of the combined left partition

    low, high = 0, m
    while low <= high:
        i = (low + high) // 2      # elements taken from nums1's left side
        j = half - i               # elements taken from nums2's left side

        # Values adjacent to the cut, with sentinels at the ends
        left1 = nums1[i - 1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j - 1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')

        if left1 <= right2 and left2 <= right1:
            # Correct partition found
            if (m + n) % 2 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2.0
        elif left1 > right2:
            high = i - 1  # took too many from nums1
        else:
            low = i + 1   # took too few from nums1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums1 = [1, 3], nums2 = [2]

    • The swap makes the shorter array [2] the search array (length 1 vs 2), so we binary search over [2] while [1, 3] is the other array. m = 1, n = 2, half = 2.
    • First cut: i = 0, j = 2 → left1 = -inf, right1 = 2, left2 = 3, right2 = +inf. left2 (3) > right1 (2), so take more from the search array: low = 1.
    • Next cut: i = 1, j = 1 → left1 = 2, right1 = +inf, left2 = 1, right2 = 3. Both conditions hold. Combined length 3 is odd, so the median is max(2, 1) = 2.0.
    • Output: 2.0

  • Input: nums1 = [1, 2], nums2 = [3, 4]

    • Same length, no swap. m = 2, n = 2, half = 2.
    • First cut: i = 1, j = 1 → left1 = 1, right1 = 2, left2 = 3, right2 = 4. left2 (3) > right1 (2), so low = 2.
    • Next cut: i = 2, j = 0 → left1 = 2, right1 = +inf, left2 = -inf, right2 = 3. Both conditions hold. Combined length 4 is even, so the median is (max(2, -inf) + min(+inf, 3)) / 2 = (2 + 3) / 2 = 2.5.
    • Output: 2.5

  • Input: nums1 = [], nums2 = [2, 4]

    • The empty array is the search array: m = 0, n = 2, half = 1. The only cut is i = 0, j = 1, giving left2 = 2, right2 = 4. Even length, so the median is (2 + 4) / 2 = 3.0.
    • Output: 3.0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume M is the length of the shorter array and N is the length of the longer array.

  • Time Complexity: O(log(min(M, N))) because we binary search only over cut positions in the shorter array, halving the search range each iteration.
  • Space Complexity: O(1) because we only track a constant number of indices and boundary values — no merged array is ever built.

Clone this wiki locally