Median of Data Stream Using Two Heaps in DSA Go - Time & Space Complexity

Time Complexity: Median of Data Stream Using Two Heaps

O(log n)

Understanding Time Complexity

We want to understand how fast we can find the middle value when numbers keep coming in.

How does the time to add numbers and get the middle change as more numbers arrive?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Add a number to the data stream
func addNum(num int) {
    if maxHeap.Len() == 0 || num <= maxHeap.Peek() {
        maxHeap.Push(num)
    } else {
        minHeap.Push(num)
    }

    // Balance the heaps
    if maxHeap.Len() > minHeap.Len()+1 {
        minHeap.Push(maxHeap.Pop())
    } else if minHeap.Len() > maxHeap.Len() {
        maxHeap.Push(minHeap.Pop())
    }
}

// Find the median
func findMedian() float64 {
    if maxHeap.Len() > minHeap.Len() {
        return float64(maxHeap.Peek())
    }
    return float64(maxHeap.Peek()+minHeap.Peek()) / 2.0
}
    

This code adds numbers to two heaps and keeps them balanced to quickly find the median.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting into heaps and balancing them.
• How many times: Each new number causes one insert and possibly one move between heaps.

How Execution Grows With Input

Each new number requires a few steps that take about the same time regardless of total numbers.

Input Size (n)	Approx. Operations
10	About 10 insertions and balancing steps
100	About 100 insertions and balancing steps
1000	About 1000 insertions and balancing steps

Pattern observation: The work grows steadily with the number of inputs, but each step stays efficient.

Final Time Complexity

Time Complexity: O(log n)

This means adding each number takes a little more time as the list grows, but still stays fast.

Common Mistake

[X] Wrong: "Adding a number is O(1) because it's just one step."

[OK] Correct: Because heaps need to keep order, adding a number requires rearranging which takes time growing with the heap size.

Interview Connect

Knowing how to keep track of the middle value quickly is a useful skill for many real-time data problems.

Self-Check

"What if we used a sorted list instead of two heaps? How would the time complexity change?"