Median of Two Sorted Arrays (K-way Merge View of the Middle Element)

• Median of Two Sorted Arrays via K-way Merge advances a two-way merge to the middle position only.
• Keep indices into both arrays, repeatedly take the smaller head, and count consumed elements.
• For odd combined length, the median is the single middle value at position n/2.
• For even combined length, the median is the average of positions n/2 - 1 and n/2.
• Time is O(M + N) linear; a binary search variant achieves O(log(min(M, N))) but is more complex.
• For money, average with BigDecimal to avoid precision loss.

What is the Median of Two Sorted Arrays problem?

Given two sorted arrays of sizes M and N, find the median of the combined sorted order without fully merging the arrays. The median is the middle value if the combined length is odd, or the average of the two middle values if even.

How does the merge-to-the-middle approach work?

We treat the two arrays as two sorted lists in a K-way merge with K equal to 2. We keep an index into each array, compare the current heads, and advance whichever is smaller. We count how many elements we have consumed and remember the last one or two values needed for the median.

package com.bank.service;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class MedianTwoArraysService {

    /**
     * Finds the median balance across two sorted regional balance lists.
     * Uses BigDecimal for precise monetary averaging.
     */
    public static BigDecimal findMedian(long[] regionA, long[] regionB) {
        int m = regionA.length, n = regionB.length;
        int total = m + n;
        int midIdx = total / 2;
        boolean isEven = (total % 2 == 0);

        int i = 0, j = 0;
        long prev = 0, curr = 0;

        for (int count = 0; count <= midIdx; count++) {
            prev = curr;
            if (j >= n || (i < m && regionA[i] <= regionB[j])) {
                curr = regionA[i++];
            } else {
                curr = regionB[j++];
            }
        }

        if (isEven) {
            BigDecimal sum = BigDecimal.valueOf(prev)
                .add(BigDecimal.valueOf(curr));
            return sum.divide(BigDecimal.valueOf(2), 2, RoundingMode.HALF_UP);
        } else {
            return BigDecimal.valueOf(curr);
        }
    }

    public static void main(String[] args) {
        long[] regionA = {10000, 25000, 50000, 75000};
        long[] regionB = {15000, 30000, 60000};
        System.out.println("Median balance: Rs. " + findMedian(regionA, regionB));
    }
}

javac -d out com/bank/service/MedianTwoArraysService.java
java -cp out com.bank.service.MedianTwoArraysService

Median balance: Rs. 30000

How do you handle odd vs even combined length?

For combined length total:

• Odd: the median is the value at consumed position total / 2 (zero-based). You need only the current value.
• Even: the median is the average of values at positions total / 2 - 1 and total / 2. You need both the previous and current values.

The loop runs midIdx + 1 iterations, keeping track of both prev and curr at each step.

Why use BigDecimal for the average?

In a banking context, balances are monetary values. Averaging two monetary amounts using floating-point arithmetic can lose precision. For example, (10001 + 10002) / 2.0 might produce 10001.5 correctly in this case, but with larger values or more decimal places, floating-point errors accumulate. BigDecimal avoids this entirely.

// WRONG for money: floating-point precision loss
double median = (prev + curr) / 2.0;

// CORRECT for money: BigDecimal precision
BigDecimal median = BigDecimal.valueOf(prev)
    .add(BigDecimal.valueOf(curr))
    .divide(BigDecimal.valueOf(2), 2, RoundingMode.HALF_UP);

What is the binary search alternative?

The binary search approach partitions both arrays such that all elements on the left partition are less than or equal to all elements on the right partition. Binary search on the shorter array finds the correct partition point in O(log(min(M, N))) time.

| Approach | Time | Space | Complexity |
|---|---|---|---|
| Merge-to-middle | O(M + N) | O(1) | Simple |
| Binary search | O(log(min(M, N))) | O(1) | Complex |

The merge view is the clean pattern-based answer. The binary search is the optimal follow-up.

What are the edge cases?

Several edge cases require attention.

• One array empty: the median is simply the middle of the non-empty array.
• Arrays of length 1: the median is the average of the two elements if both have one element.
• All elements equal: the median equals that common value.
• Disjoint ranges: one array is entirely less than the other; the merge is trivial.

package com.bank.core;

import java.math.BigDecimal;

public class MedianEdgeCases {
    public static void main(String[] args) {
        // One empty array
        System.out.println(MedianTwoArraysService.findMedian(
            new long[]{10000, 20000, 30000}, new long[]{})); // 20000

        // Both single-element
        System.out.println(MedianTwoArraysService.findMedian(
            new long[]{10000}, new long[]{20000})); // 15000.00
    }
}

20000
15000.00

What is the time and space complexity?

The merge-to-the-middle approach runs in O(M + N) time because we advance through both arrays up to the midpoint. Space is O(1) since we only track indices and the previous/current values. The binary search approach runs in O(log(min(M, N))) time with O(1) space.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• The merge view is K-way Merge with K=2: framing it this way connects the problem to the broader pattern family.
• Binary search correctness: the partition must satisfy maxLeft <= minRight for both arrays, with sentinel values for boundary cases.
• Generalization to K arrays: finding the median of K sorted arrays can use a full K-way merge to the middle or more sophisticated techniques.
• Overflow: when summing two values for the average, use long or BigDecimal to prevent integer overflow.

What are common interview follow-up questions?

Interviewers often extend this problem.

• Kth smallest element in two sorted arrays: generalize the merge-to-the-middle to stop at position K.
• Median of a stream: use two heaps (max-heap and min-heap) to maintain the median as elements arrive.
• Weighted median: each element has a weight, and the median accounts for weights.