LeetCode 101: 295 Find Median from Data Stream

LeetCode Problem: 295. Find Median from Data Stream

https://leetcode.com/problems/find-median-from-data-stream/description/

Problem Description:

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 average of the two middle values.

Implement a data structure that supports the following operations:

• addNum(int num): Add a integer number from the data stream to the data structure.
• findMedian(): Return the median of all elements so far.

Example:

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);
medianFinder.addNum(2);
medianFinder.findMedian(); // return 1.5
medianFinder.addNum(3); 
medianFinder.findMedian(); // return 2

Original Code (Using Heaps):

import heapq

class MedianFinder:

    def __init__(self):
        self.small, self.large = [], []  # Create two heaps: small (max-heap) and large (min-heap)

    def addNum(self, num: int) -> None:
        if self.large and num > self.large[0]:
            heapq.heappush(self.large, num)  # Push to the large heap (min-heap)
        else:
            heapq.heappush(self.small, -1 * num)  # Push to the small heap (max-heap, store negative values)

        # Balance the heaps
        if len(self.small) > len(self.large) + 1:
            val = -1 * heapq.heappop(self.small)  # Remove the largest from small
            heapq.heappush(self.large, val)  # Add it to large
        if len(self.large) > len(self.small) + 1:
            val = heapq.heappop(self.large)  # Remove the smallest from large
            heapq.heappush(self.small, -1 * val)  # Add it to small

    def findMedian(self) -> float:
        # Find the median based on the sizes of the heaps
        if len(self.small) > len(self.large):
            return -1 * self.small[0]  # Return the largest element in small
        elif len(self.large) > len(self.small):
            return self.large[0]  # Return the smallest element in large
        return (-1 * self.small[0] + self.large[0]) / 2.0  # Return the average of both heaps

Line-by-Line Explanation and Example Execution:

1. import heapq

   • Imports the heapq module to utilize heaps.

2. class MedianFinder:

   • Defines the MedianFinder class.

3. def __init__(self):

   • Initializes the data structure.

4. self.small, self.large = [], []

   • Creates two heaps:
     • self.small: a max-heap (simulated using negative values).
     • self.large: a min-heap.

5. def addNum(self, num: int) -> None:

   • Defines the method to add a number to the data structure.

6. if self.large and num > self.large[0]:

   • Checks if num is greater than the smallest element in the large heap.

7. heapq.heappush(self.large, num)

   • If true, adds num to the large heap.

8. else:

   • If num is less than or equal to the smallest in large, adds -1 * num to small.

9. Balancing the Heaps:

   • Checks the sizes of the heaps and balances them if necessary:

     if len(self.small) > len(self.large) + 1:
     val = -1 * heapq.heappop(self.small)
     heapq.heappush(self.large, val)
     if len(self.large) > len(self.small) + 1:
     val = heapq.heappop(self.large)
     heapq.heappush(self.small, -1 * val)

10. def findMedian(self) -> float:

    • Defines the method to find the median.

11. Finding the Median:

    • Determines the median based on the sizes of the heaps:

      if len(self.small) > len(self.large):
      return -1 * self.small[0]
      elif len(self.large) > len(self.small):
      return self.large[0]
      return (-1 * self.small[0] + self.large[0]) / 2.0

Example Execution:

Assuming we perform the following operations:

1. Add Numbers:
   • medianFinder.addNum(1):
     • self.small = [-1], self.large = [].
   • medianFinder.addNum(2):
     • self.small = [-1], self.large = [2].
   • medianFinder.findMedian():
     • Returns (1 + 2) / 2 = 1.5.
   • medianFinder.addNum(3):
     • self.small = [-1], self.large = [2, 3].
   • medianFinder.findMedian():
     • Returns 2.

Time Complexity Analysis:

• Time Complexity: O(log n)
  • Each addition of a number takes O(log n) time due to the heap operations.

Space Complexity Analysis:

• Space Complexity: O(n)
  • In the worst case, both heaps could store all the numbers.

Tips and Warnings:

1. Edge Cases:

   • Consider the case of an empty data structure before calling findMedian().

2. Understanding Heaps:

   • Ensure you understand how max-heaps and min-heaps are utilized to find the median.

3. Efficiency:

   • This approach efficiently maintains the balance between two heaps to allow quick median retrieval.

Summary

• Heap Method: Effectively maintains a data stream to find the median, with a time complexity of O(log n) for insertion and O(1) for finding the median.
• Clear and Understandable: The code is straightforward and easy to follow, suitable for this type of problem.

Application Tips

1. Choose Appropriate Methods:

   • Select the method best suited to specific problem requirements to ensure efficiency and readability.

2. Handle Edge Cases:

   • Always consider edge cases in algorithm design to avoid potential errors.

3. Optimize Space Usage:

   • When handling large datasets, consider using space-efficient algorithms.