Introduction

In this blog post, we will explore how to solve the LeetCode problem "295" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 all elements so far. Answers within 10-5 of the actual answer will be accepted. Example 1: Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0 Constraints: -105 <= num <= 105 There will be at least one element in the data structure before calling findMedian. At most 5 * 104 calls will be made to addNum and findMedian. Follow up: If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

Explanation

Here's a breakdown of the solution, followed by the Python code:

• High-Level Approach:

  • Use two heaps: a max-heap to store the smaller half of the numbers and a min-heap to store the larger half.
  • Maintain the balance of the heaps: either the heaps have the same size, or the max-heap has one more element. This allows for easy median calculation.
  • addNum() inserts the new number into the appropriate heap and rebalances to maintain the size property. findMedian() returns the median based on the heap structure.

• Complexity:

  • Runtime: addNum is O(log n), findMedian is O(1). Storage: O(n)

Code

    import heapq

class MedianFinder:

    def __init__(self):
        """
        Initialize data structure here.
        """
        self.small = []  # max-heap stores the smaller half of the numbers
        self.large = []  # min-heap stores the larger half of the numbers

    def addNum(self, num: int) -> None:
        """
        Adds the integer num from the data stream to the data structure.
        """
        # Add to the max-heap (negate to simulate max-heap)
        heapq.heappush(self.small, -num)

        # Ensure every number in small is <= every number in large
        if self.large and -self.small[0] > self.large[0]:
            heapq.heappush(self.large, -heapq.heappop(self.small))

        # Balance the sizes
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        elif len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        """
        Returns the median of all elements so far.
        """
        if len(self.small) == len(self.large):
            return (-self.small[0] + self.large[0]) / 2.0
        else:
            return -self.small[0]