Leetcode TLE with python 2. It accepts with python 3.

PriyankaKhire · PriyankaKhire · commit e68eec631e72 · 2021-08-25T18:25:44.000-07:00
diff --git a/Blind 75/Programs/Find Median from Data Stream.py b/Blind 75/Programs/Find Median from Data Stream.py
@@ -0,0 +1,75 @@
+# Find Median from Data Stream
+# https://leetcode.com/problems/find-median-from-data-stream/
+
+class MedianFinder(object):
+
+    def __init__(self):
+        # holds all elements greater than median
+        self.minHeap = []
+        # holds all elements smaller than median.
+        self.maxHeap = []
+        """
+        initialize your data structure here.
+        """
+    
+    def addToMinHeap(self, num):
+        # add number to min heap
+        heapq.heappush(self.minHeap, num)
+        # if length of heap is more then pop the element and add to max heap
+        if (len(self.minHeap) > len(self.maxHeap)+1):
+            element = heapq.heappop(self.minHeap)
+            self.addToMaxHeap(element)
+    
+    def addToMaxHeap(self, num):
+        # add number to max heap
+        self.maxHeap.append(num)
+        heapq._heapify_max(self.maxHeap)
+        # if length of heap is more then pop the item and add to min Heap
+        if (len(self.maxHeap) > len(self.minHeap)+1):
+            element = self.maxHeap.pop(0)
+            heapq._heapify_max(self.maxHeap)
+            self.addToMinHeap(element)
+        
+    def addNum(self, num):
+        # if both heaps are empty
+        if ((not self.minHeap) and (not self.maxHeap)):
+            self.addToMinHeap(num)
+            return
+        # if max heap is empty but min heap is not.
+        if ((not self.maxHeap) and self.minHeap):
+            # if top of min heap < num (because min heap needs to hold elements greater than median)
+            if (self.minHeap[0] < num):
+                # pop the top from min heap and add to max heap
+                topMinElement = heapq.heappop(self.minHeap)
+                self.addToMaxHeap(topMinElement)
+            # add current element to min heap
+            self.addToMinHeap(num)
+            return
+        # if both heaps have elements
+        if (self.minHeap and self.maxHeap):
+            # max heap contains elements from 0 to median
+            if (num < self.maxHeap[0]):
+                self.addToMaxHeap(num)
+            else:
+                self.addToMinHeap(num)
+        """
+        :type num: int
+        :rtype: None
+        """
+        
+    def findMedian(self):
+        if (len(self.minHeap) == len(self.maxHeap)):
+            return float(self.minHeap[0]+self.maxHeap[0])/float(2)
+        if (len(self.minHeap) > len(self.maxHeap)):
+            return self.minHeap[0]
+        return self.maxHeap[0]
+        """
+        :rtype: float
+        """
+        
+
+
+# Your MedianFinder object will be instantiated and called as such:
+# obj = MedianFinder()
+# obj.addNum(num)
+# param_2 = obj.findMedian()
diff --git a/Blind 75/README.md b/Blind 75/README.md
@@ -1,6 +1,6 @@
 <h1>Blind 75</h1>
   <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Leetcode link to the post.</a>
-  <h4>Total Completed: 29</h4>
+  <h4>Total Completed: 31</h4>
   <h2>Array (Solved: 4, Unsolved: 6)</h2>
     <ul>
       <li><a href="Programs/Two Sum.py">Two Sum</a> 
@@ -284,7 +284,7 @@
       <li>Add and Search Word</li>
       <li>Word Search II</li>
     </ul>
-  <h2>Heap (Solved: 1, Unsolved: 2)</h2>
+  <h2>Heap (Solved: 2, Unsolved: 1)</h2>
     <ul>
       <li><a href="Programs/Merge K sorted Lists.py">Merge K Sorted Lists</a> </li>
       <li><a href="Programs/Top K Frequent Elements.py">Top K Frequent Elements</a> 
@@ -293,7 +293,13 @@
           Remove the top k elements from the heap.
         </p>
       </li>
-      <li>Find Median from Data Stream</li>
+      <li><a href="Programs/Find Median from Data Stream.py">Find Median from Data Stream</a> 
+        <p><b>Approach</b>: Keep 2 heaps, max heap to hold all elements less than median and min heap to hold elements greater than the median. <br/>
+          Finding median: which ever heap has more elements, the top element of that heap is the median. <br/>
+          If both heaps have same elements, then median is (minHeapTop+maxHeapTop) / 2 <br/>
+          If at any point one heap has 2 elements more than other heap, pop an element from that heap and add it to another heap.
+        </p>
+      </li>
     </ul>
 
 
