{"id":4853,"date":"2021-12-17T16:44:17","date_gmt":"2021-12-17T11:14:17","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4853"},"modified":"2022-01-17T13:22:25","modified_gmt":"2022-01-17T07:52:25","slug":"find-median-in-a-stream","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/find-median-in-a-stream\/","title":{"rendered":"Find Median in a Stream"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-sorting\">Approach 1: Sorting<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-insertion-sort\">Approach 2: Insertion Sort<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#approach-3-two-heaps\">Approach 3: Two Heaps<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-two-heaps\">C++ Code For Two Heaps<\/a><\/li><li><a href=\"#java-code-for-two-heaps\">Java Code For Two Heaps<\/a><\/li><li><a href=\"#python-code-for-two-heaps\">Python Code For Two Heaps<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given are some integers, which are read from the data stream. The task is to find the median of the integers read so far.<\/p>\n\n\n\n<p>The <strong>median<\/strong> is the middle value of a sorted list of integers. If the size of the list is even, the median is the average of the two middle elements.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input:<\/strong> [1, 2, 3,\u2026]<br><strong>Output:<\/strong> [1, 1.5, 2..]<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<ul><li>The list contains [1]. So, median = 1 \/ 1 = 1<\/li><li>The list contains [1, 2]. Median = (1 + 2) \/ 2 = 1.5<\/li><li>The list contains [1, 2, 3]. Median = (1 + 2 + 3) \/ 3 = 2<\/li><\/ul>\n\n\n\n<h2 id=\"approach-1-sorting\">Approach 1: Sorting<\/h2>\n\n\n\n<p>The most basic approach is to store the integers in a list and sort the list every time for calculating the median.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialize a list for storing the integers.<\/li><li>Sort the list every time.<\/li><li>Print the median.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class MedianFinder {\n  vector &lt; int > store;\n \n  public:\n    void addNum(int num) {\n      store.push_back(num);\n    }\n  double findMedian() {\n    sort(store.begin(), store.end());\n \n    int n = store.size();\n    return (n &amp; 1 ? store[n \/ 2] : ((double) store[n \/ 2 - 1] + store[n \/ 2]) * 0.5);\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> class MedianFinder {\n  List &lt; Integer > input = new ArrayList &lt; > ();\n \n  public void addNum(int num) {\n    input.add(num);\n  }\n \n  public double findMedian() {\n    Collections.sort(input);\n    int len = input.size();\n    if (len % 2 == 1) return input.get(len \/ 2);\n    return 0.5 * (input.get(len \/ 2) + input.get(len \/ 2 - 1));\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class MedianFinder:\n    def __init__(self):\n        self.array = []\n \n    def addNum(self, num: int) -> None:\n        self.array.append(num)\n \n    def findMedian(self) -> float:\n        self.array.sort()\n        n = len(self.array)\n        if not self.array or n == 1:\n            return 0 or self.array[0]\n        elif n &amp; 1:\n            return self.array[n \/\/ 2]\n        else:\n            return (self.array[n \/\/ 2] + self.array[(n \/\/ 2) - 1]) \/ 2<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(NlogN), where N is a number of elements.<br><strong>Space Complexity:<\/strong>O(N), for storing list.<\/p>\n\n\n\n<h2 id=\"approach-2-insertion-sort\">Approach 2: Insertion Sort<\/h2>\n\n\n\n<p>In the previous approach, we sorted the list every time. Instead of sorting, we can insert the item in their specific position to keep the list always sorted.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>We assume the list is already sorted.<\/li><li>When a new integer comes up, apply binary search to insert the integer in its correct position.<\/li><li>Now, the list is sorted and you can find the median.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class MedianFinder {\n  vector &lt; int > store;\n \n  public:\n    void addNum(int num) {\n      if (store.empty())\n        store.push_back(num);\n      else\n        store.insert(lower_bound(store.begin(), store.end(), num), num);\n    }\n  double findMedian() {\n    int n = store.size();\n    return n &amp; 1 ? store[n \/ 2] : ((double) store[n \/ 2 - 1] + store[n \/ 2]) * 0.5;\n  }\n};<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> class MedianFinder {\n  List &lt; Integer > data;\n  public MedianFinder() {\n    data = new ArrayList();\n  }\n \n  public void addNum(int num) {\n    int idx = Collections.binarySearch(data, num);\n    if (idx >= 0) {\n      data.add(idx, num);\n    } else {\n      data.add(-idx - 1, num);\n    }\n  }\n \n  public double findMedian() {\n    int len = data.size();\n    int mid = data.get(len \/ 2);\n    if (len % 2 == 1) {\n      return mid;\n    } else {\n      return 1.0 * ((data.get(len \/ 2 - 1)) + mid) \/ 2;\n    }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">class MedianFinder:\n    def __init__(self):\n        self.q = []\n \n    def addNum(self, num):\n        bisect.insort(self.q, num)\n \n    def findMedian(self):\n        n = len(self.q)\n        m = n >> 1\n        return self.q[m] if n &amp; 1 else (self.q[m - 1] + self.q[m]) \/ 2<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is a number of elements.<br><strong>Space Complexity:<\/strong> O(N), for storing list.<\/p>\n\n\n\n<h2 id=\"approach-3-two-heaps\">Approach 3: Two Heaps<\/h2>\n\n\n\n<p>The idea is to use a <strong>max heap<\/strong> and a <strong>min-heap<\/strong>. <strong>Max heap<\/strong> is used to store the smaller half of the number and the <strong>min-heap<\/strong> is used to store the larger half of the numbers.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>If the current element to be added is less than the maximum element of the max heap, then add this to the max heap.<\/li><li>If the difference between the size of the max and min heap becomes greater than 1, the top element of the max heap is removed and added to the min-heap.<\/li><li>If the current element to be added is greater than the maximum element of the min-heap, then add this to the min-heap.<\/li><li>If the difference between the size of the max and min heap becomes greater than 1, the top element of the min-heap is removed and added to the max heap.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-two-heaps\">C++ Code For Two Heaps<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void findMedian(int arr[], int n) {\n  priority_queue &lt; int > lowerHalf;\n  priority_queue &lt; int, vector &lt; int > , greater &lt; int >> higherHalf;\n \n  int median;\n  for (int size = 1; size &lt;= n; size++) {\n    if (!lowerHalf.empty() &amp;&amp; lowerHalf.top() > arr[size - 1]) {\n      lowerHalf.push(arr[size - 1]);\n \n      if (lowerHalf.size() > higherHalf.size() + 1) {\n        higherHalf.push(lowerHalf.top());\n        lowerHalf.pop();\n      }\n    } else {\n      higherHalf.push(arr[size - 1]);\n \n      if (higherHalf.size() > lowerHalf.size() + 1) {\n        lowerHalf.push(higherHalf.top());\n        higherHalf.pop();\n      }\n    }\n    if (size % 2 == 1) {\n      if (higherHalf.size() > lowerHalf.size()) {\n        median = higherHalf.top();\n      } else {\n        median = lowerHalf.top();\n      }\n    } else {\n      median = (lowerHalf.top() + higherHalf.top()) \/ 2;\n    }\n    cout &lt;&lt; median &lt;&lt; \" \";\n  }\n}<\/pre>\n\n\n\n<h3 id=\"java-code-for-two-heaps\">Java Code For Two Heaps<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public class Solution {\n \n  public static void findMedian(int arr[]) {\n    int n = arr.length;\n \n    PriorityQueue &lt; Integer > lowerHalf = new PriorityQueue &lt; > (new Comparator &lt; Integer > () {\n      @Override\n      public int compare(Integer first, Integer second) {\n        return (second - first);\n      }\n    });\n \n    PriorityQueue &lt; Integer > higherHalf = new PriorityQueue &lt; > ();\n \n    int median;\n    for (int size = 1; size &lt;= n; size++) {\n      if (!lowerHalf.isEmpty() &amp;&amp; lowerHalf.peek() > arr[size - 1]) {\n        lowerHalf.add(arr[size - 1]);\n \n        if (lowerHalf.size() > higherHalf.size() + 1) {\n          higherHalf.add(lowerHalf.poll());\n        }\n      } else {\n        higherHalf.add(arr[size - 1]);\n \n        if (higherHalf.size() > lowerHalf.size() + 1) {\n          lowerHalf.add(higherHalf.poll());\n        }\n      }\n      if (size % 2 == 1) {\n        if (higherHalf.size() > lowerHalf.size()) {\n          median = higherHalf.peek();\n        } else {\n          median = lowerHalf.peek();\n        }\n      } else {\n        median = (lowerHalf.peek() + higherHalf.peek()) \/ 2;\n      }\n      System.out.print(median + \" \");\n    }\n  }\n \n}<\/pre>\n\n\n\n<h3 id=\"python-code-for-two-heaps\">Python Code For Two Heaps<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">from queue import PriorityQueue\n \nINT_MAX = 10000000000\n \n \ndef findMedian(arr, n):\n    lowerHalf = PriorityQueue()\n    higherHalf = PriorityQueue()\n    for size in range(1, n + 1):\n \n        x = INT_MAX\n        if lowerHalf.qsize() > 0:\n \n            x = abs(lowerHalf.get())\n            lowerHalf.put(-x)\n \n        if lowerHalf.qsize() > 0 and x > arr[size - 1]:\n            lowerHalf.put(-(arr[size - 1]))\n \n            if lowerHalf.qsize() > higherHalf.qsize() + 1:\n                higherHalf.put(abs(lowerHalf.get()))\n \n        else:\n \n            higherHalf.put(arr[size - 1])\n \n            if higherHalf.qsize() > lowerHalf.qsize() + 1:\n                lowerHalf.put(-(higherHalf.get()))\n \n        if size % 2 == 1:\n \n            if higherHalf.qsize() > lowerHalf.qsize():\n \n                median = higherHalf.get()\n                higherHalf.put(median)\n \n            else:\n \n                median = abs(lowerHalf.get())\n                lowerHalf.put(-median)\n \n        else:\n \n            a = lowerHalf.get()\n            lowerHalf.put(a)\n            b = higherHalf.get()\n            higherHalf.put(b)\n \n            median = (abs(a) + b) \/\/ 2\n \n        print(median, end=\" \")<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(NlogN), where N is the number of elements.<br><strong>Space Complexity:<\/strong> O(N), for storing lists.<\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. What is a median?<\/strong><br>A. The median is the middle value of a sorted list of integers. If the size of the list is even, the median is the average of the two middle elements.<\/p>\n\n\n\n<p><strong>Q. What is the most efficient approach to solving this problem?<\/strong><br>A. The approach using a min-heap and max heap is the most efficient approach to solve the problem. The time complexity is O(logN) and the space complexity is O(N).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given are some integers, which are read from the data stream. The task is to find&hellip;\n","protected":false},"author":5,"featured_media":5099,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[677],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4853"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4853"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4853\/revisions"}],"predecessor-version":[{"id":5946,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4853\/revisions\/5946"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5099"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}