What is the time complexity of Find Median from Data Stream?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Find Median from Data Stream?

This problem uses Two Pointers, Design, Sorting, Heap (Priority Queue), Data Stream. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Find Median from Data Stream?

Insight 1: Using two heaps (a max-heap and a min-heap) allows efficient tracking of the smaller and larger halves of the data stream, enabling quick median calculation. Insight 2: Maintaining a balanced state between the two heaps, where the max-heap contains the smaller half of the numbers and the min-heap contains the larger half, is crucial for determining the median in O(1) time.

Which companies ask LeetCode 295. Find Median from Data Stream in interviews?

This problem is frequently asked at Agoda, Anduril, Citadel, Cohesity, Coupang and 18 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find Median from Data Stream - LeetCode 295 Solution

Find Median from Data Stream - Complete Solution Guide

Find Median from Data Stream is LeetCode problem 295, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. For example, for arr = [2,3,4] , the median is 3 . For example, for arr = [2,3] , the median is (2 + 3) / 2 = 2.5 . Implement the MedianFinder class: MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure. double findMedian() returns the median of

Detailed Explanation

The problem requires designing a `MedianFinder` class that efficiently calculates the median of a stream of numbers. The `addNum(int num)` method adds a new number to the data structure, and the `findMedian()` method returns the median of all the numbers added so far. If the number of elements is odd, the median is the middle element. If the number of elements is even, the median is the average of the two middle elements. The solution needs to handle a large number of calls to `addNum` and `findMedian` efficiently.

Solution Approach

The solution employs two heaps: `small_half` (a max-heap) and `large_half` (a min-heap). `small_half` stores the smaller half of the numbers seen so far, and `large_half` stores the larger half. The algorithm maintains the invariant that all elements in `small_half` are less than or equal to all elements in `large_half`. When a new number is added, it's initially added to `small_half`. Then, the largest element of `small_half` is moved to `large_half`. After that, the sizes of the two heaps are balanced so that `small_half` either has the same number of elements as `large_half` or one more element. The median is then found by either returning the top element of `small_half` if the total number of elements is odd, or the average of the top elements of `small_half` and `large_half` if the total number of elements is even.

Step-by-Step Algorithm

Step 1: Initialize two priority queues (heaps): `small_half` as a max-heap and `large_half` as a min-heap.
Step 2: `addNum(num)`: Add the new number to the `small_half` (max-heap).
Step 3: Move the largest element from `small_half` to `large_half` to maintain the ordering property.
Step 4: Balance the heaps. If the `large_half` is larger than `small_half`, move the smallest element from `large_half` to `small_half`.
Step 5: `findMedian()`: If `small_half` has more elements, the median is the top of `small_half`. Otherwise, the median is the average of the top elements of `small_half` and `large_half`.

Key Insights

Insight 1: Using two heaps (a max-heap and a min-heap) allows efficient tracking of the smaller and larger halves of the data stream, enabling quick median calculation.
Insight 2: Maintaining a balanced state between the two heaps, where the max-heap contains the smaller half of the numbers and the min-heap contains the larger half, is crucial for determining the median in O(1) time.
Insight 3: The sizes of the two heaps should be either equal or the max-heap (smaller half) has one more element. This property guarantees correct median calculation.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(n)

Topics

This problem involves: Two Pointers, Design, Sorting, Heap (Priority Queue), Data Stream.

Companies

Asked at: Agoda, Anduril, Citadel, Cohesity, Coupang, Docusign, Goldman Sachs, Google, IXL, KLA, Nvidia, Okta, PayPal, Pinterest, Salesforce, Samsung, Snowflake, Splunk, Spotify, StackAdapt, Tinder, Twitch, WorldQuant.

Find Median from Data Stream | LeetCode 295

Hard

Two Pointers Design Sorting Heap (Priority Queue)Data Stream

Time: O(log n)Space: O(n)

Solution Code

Available in:

import java.util.PriorityQueue;
import java.util.Collections;

class MedianFinder {

    private PriorityQueue<Integer> small_half; // max-heap for the smaller half of numbers
    private PriorityQueue<Integer> large_half; // min-heap for the larger half of numbers

    public MedianFinder() {
        small_half = new PriorityQueue<>(Collections.reverseOrder());
        large_half = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // Add the new number to the max-heap (small_half)
        small_half.add(num);
        
        // To maintain the property that all numbers in small_half are <= all numbers in large_half,
        // move the largest element from small_half to large_half.
        large_half.add(small_half.poll());
        
        // Balance the heaps to maintain the size invariant:
        // len(small_half) is either equal to or one greater than len(large_half).
        if (large_half.size() > small_half.size()) {
            small_half.add(large_half.poll());
        }
    }
    
    public double findMedian() {
        // If the total number of elements is odd, the median is at the top of the small_half.
        if (small_half.size() > large_half.size()) {
            return (double) small_half.peek();
        }
        // If the total number of elements is even, the median is the average of the
        // tops of the two heaps.
        else {
            return (small_half.peek() + large_half.peek()) / 2.0;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 295: Find Median from Data Stream - Detailed explanation and solution approaches.

Topics

Two Pointers Design Sorting Heap (Priority Queue)Data Stream

Companies

AgodaAndurilCitadelCohesityCoupangDocusignGoldman SachsGoogle

Stats

Difficulty:Hard

Languages:4

Companies:23

Problem #:295

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize two priority queues (heaps): `small_half` as a max-heap and `large_half` as a min-heap.
2
Step 2: `addNum(num)`: Add the new number to the `small_half` (max-heap).
3
Step 3: Move the largest element from `small_half` to `large_half` to maintain the ordering property.
4
Step 4: Balance the heaps. If the `large_half` is larger than `small_half`, move the smallest element from `large_half` to `small_half`.
5
Step 5: `findMedian()`: If `small_half` has more elements, the median is the top of `small_half`. Otherwise, the median is the average of the top elements of `small_half` and `large_half`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The `addNum` operation involves heap push and pop operations, which take O(log n) time. The `findMedian` operation only requires accessing the top elements of the heaps, which takes O(1) time. The space complexity is O(n) because we store all the numbers in the two heaps, and in the worst-case scenario, the number of stored elements will be equal to the number of `addNum` calls, i.e., n. The C implementation using a fixed capacity heap would be O(1) space if the number of added elements is less than the capacity, but at the cost of potentially losing elements.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorted Array

Store the numbers in a sorted array. Insertion would involve finding the correct position to insert, maintaining the sorted order.

Time: O(n) for addNum (insertion), O(1) for findMedian (accessing middle element(s)).Space: O(n)

Trade-offs: The array approach is simpler to implement for smaller datasets, but the O(n) insertion time makes it less efficient for large streams compared to the heap-based solution's O(log n) insertion time. The sorted array approach could be useful if queries are significantly more frequent than insertions because findMedian is O(1) in this scenario.

Self-Balancing Binary Search Tree (BST)

Use a self-balancing BST to maintain the numbers in sorted order. Insertion and finding the k-th smallest element (needed for median) can be done efficiently.

Time: O(log n) for addNum (insertion), O(log n) for findMedian (finding k-th element).Space: O(n)

Trade-offs: BSTs provide similar performance to heaps but can be more complex to implement and might have higher constant factors. Heaps are often preferred for this specific problem due to their simplicity and efficiency.

✨

Key Insights

1Insight 1: Using two heaps (a max-heap and a min-heap) allows efficient tracking of the smaller and larger halves of the data stream, enabling quick median calculation.
2Insight 2: Maintaining a balanced state between the two heaps, where the max-heap contains the smaller half of the numbers and the min-heap contains the larger half, is crucial for determining the median in O(1) time.
3Insight 3: The sizes of the two heaps should be either equal or the max-heap (smaller half) has one more element. This property guarantees correct median calculation.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty stream initially. The initialization of heaps handles this case, and addNum takes care to insert an element. The findMedian function will only be called when there is at least one element so this is not a special case.
Edge case 2: Adding duplicate numbers. The solution correctly handles duplicate numbers as the heaps maintain the relative order, and the balancing ensures the median is calculated correctly.
Edge case 3: The C solution may run into overflow if the max heap size is reached

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using only one heap. A single heap cannot efficiently track both the smaller and larger halves of the data stream simultaneously to determine the median.

✗Common mistake 2: Incorrectly balancing the heaps. If the heaps are not balanced correctly (i.e., small_half having the same number of elements as large_half or one more), the median calculation will be wrong.

✗Common mistake 3: Forgetting to move the largest element from `small_half` to `large_half` after adding a new number to `small_half`. This step is crucial to maintain the ordering property between the two heaps.

✗Common mistake 4: Not considering the integer overflow issue when calculating the average of the two medians if the sum of two numbers exceeds the MAX_INT limit.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Real-time stock market analysis. The median price of a stock can be tracked as new transactions occur, providing a robust measure that is less sensitive to extreme outliers than the average.

🏦Real-world scenario 2: Monitoring network latency. Tracking the median latency of network requests can help identify performance issues while mitigating the impact of occasional high-latency requests.

🎮Real-world scenario 3: Calculating rolling medians in financial time series data. This can smooth out noise and reveal underlying trends more effectively than simple moving averages.

📱Real-world scenario 4: Anomaly detection: The median can be used to define a 'normal' range of values, and data points that deviate significantly from the median can be flagged as anomalies.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The two-pointer technique is powerful for sorted arrays. The key insight is recognizing when elements can be processed from both ends simultaneously.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

The most common mistake is not handling the case when pointers meet. Always consider the termination condition.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 24, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 30

❓

Frequently Asked Questions

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Find Median from Data Stream"?

For this hard-level Two Pointers problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether design techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?