Introduction

Median questions become tricky when the data is not presented as one already sorted list. The definition is still simple, but the algorithm changes depending on whether you have a stream, two sorted arrays, or only partial access to the data. That is why many interview-style "median" problems are really questions about data structures and algorithm design.

Start with the Definition, Not the Trick

For an odd number of values, the median is the middle value after sorting. For an even number of values, it is the average of the two middle values.

1def median(values):
2    values = sorted(values)
3    n = len(values)
4    mid = n // 2
5    if n % 2 == 1:
6        return values[mid]
7    return (values[mid - 1] + values[mid]) / 2
8
9print(median([7, 1, 9, 3]))

This solves the basic problem correctly. It becomes inefficient only when the input is large, streaming, or already partially structured in a way that lets you do better.

Streaming Median Uses Two Heaps

A classic tricky version asks for the median after each new number arrives. Re-sorting the full list every time is too slow. The standard solution uses two heaps: one max-heap for the lower half and one min-heap for the upper half.

1import heapq
2
3class RunningMedian:
4    def __init__(self):
5        self.low = []
6        self.high = []
7
8    def add(self, value):
9        heapq.heappush(self.low, -value)
10        heapq.heappush(self.high, -heapq.heappop(self.low))
11        if len(self.high) > len(self.low):
12            heapq.heappush(self.low, -heapq.heappop(self.high))
13
14    def median(self):
15        if len(self.low) > len(self.high):
16            return -self.low[0]
17        return (-self.low[0] + self.high[0]) / 2

The trick is balance. The heaps must differ in size by at most one element, and every value in the lower half must stay less than or equal to every value in the upper half.

Two Sorted Arrays Need a Different Idea

Another common median puzzle gives you two sorted arrays and asks for the median of their union without fully merging them. You can solve that in linear time by merging until the middle, but the more interesting solution uses a partition-based binary search.

The key insight is that you do not need the full merged array. You only need a partition where the left side contains exactly half the elements and every left-side value is less than or equal to every right-side value.

That is why the problem feels tricky: it looks statistical, but the efficient solution is really about partition conditions.

Be Careful with Even Length and Duplicates

Median bugs often come from edge cases, not from the main idea. Even-length inputs require averaging two middle values. Duplicate elements are fine, but comparisons must still preserve ordering logic. Empty input should usually raise an error instead of pretending there is a meaningful median.

1def safe_median(values):
2    if not values:
3        raise ValueError("median is undefined for empty input")
4    return median(values)

These cases matter because many incorrect solutions work on the happy path and fail only when the input is small or symmetric.

Ask What Access Model the Problem Allows

A strong way to approach a tricky median question is to ask what kind of access the problem grants. Can you sort? Are the arrays already sorted? Is the data streaming? Do you need the exact median or an approximation?

Those details determine the algorithm. Without them, you can waste time optimizing the wrong version of the problem.

That is also why the naive solution is still valuable. It gives you a correct baseline. Once you state it clearly, you can justify when a more advanced structure such as heaps or binary search is worth the extra complexity.

Common Pitfalls

• Jumping to a clever algorithm before restating the exact median definition.
• Forgetting the even-length case and returning only one middle element.
• Using a streaming approach when the input is actually static and easy to sort once.
• Ignoring empty-input behavior.
• Treating median problems as formula puzzles when they are often data-access problems.

Summary

• The definition of median is simple, but the best algorithm depends on the input model.
• For ordinary static data, sorting and taking the middle is often enough.
• For streaming data, two heaps are the standard exact solution.
• For two sorted arrays, efficient solutions rely on partition logic rather than full merging.
• Clarify the access constraints before choosing the algorithm.