D
DevExCode

LeetCode 295: Find Median from Data Stream Solution

Master LeetCode problem 295 (Find Median from Data Stream), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To find the median from a data stream efficiently, we can use two priority queues - one max heap to store the lower half of the elements and one min heap to store the higher half of the elements. By maintaining these two heaps, we can obtain the median in constant time.

Here's how the algorithm works:

  1. Initialize two priority queues: maxHeap to store the smaller half of elements and minHeap to store the larger half of elements.
  2. When adding a new number:
    • Add the number to maxHeap.
    • If the size of maxHeap is greater than the size of minHeap or the top element of maxHeap is greater than the new number, pop the top element from maxHeap and push it to minHeap.
    • If the size of minHeap is greater than the size of maxHeap, pop the top element from minHeap and push it to maxHeap.
  3. To find the median:
    • If the size of maxHeap and minHeap is the same, return the average of their top elements.
    • Otherwise, return the top element of the heap with more elements.

Solution Code

import java.util.PriorityQueue;

class MedianFinder {
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 295 (Find Median from Data Stream)?

This page provides optimized solutions for LeetCode problem 295 (Find Median from Data Stream) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 295 (Find Median from Data Stream)?

The time complexity for LeetCode 295 (Find Median from Data Stream) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 295 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 295 in Java, C++, or Python.

Back to LeetCode Solutions