Given that integers are being read from a data stream. Find the median of all the elements read so far starting from the first integer until the last integer. This is also called Median of Running Integers. The given link already contains solution of this problem using Priority Queue. However, the following solution uses the same concept but the implementation is by using sets. In this solution, we will print the smaller median in case of even length instead of taking their average.
Examples:
Input: arr[] = {-10, 14, 11, -5, 7}
Output: -10 -10 11 -5 7Input: arr[] = {2, -5, 14}
Output: 2 -5 2
Approach:
- Create two multisets g in ascending order that will store the upper half and s in descending order to store the lower half of the array arr[].
- Insert the first element in s. And initialize the median with this value.
- For every other element of the array x. Check the sizes of both the sets:
- When size(s) > size(g): If x > median then insert the first element of s into g and remove that element from s, insert x into s. Else insert x into g.Median = top/begin of set with larger size.
- When size(s) < size(g): If x < median then insert the first element of g into s and remove that element from g, insert x into g. Else insert x into s. Median = top/begin of set with larger size.
- When size(s) = size(g): If x > median. Insert x into s, Median = begin of g. Else insert x into g.
Below is the implementation of the above approach:
CPP
// C++ program to find running median for// a stream of integers using Set#include <bits/stdc++.h>using namespace std;// Function to print the running median// for the array arr[]void printRunningMedian(int arr[], int n){ // Multiset is used to handle duplicates // Multiset g for storing upper half // (ascending order) // The first element will be the smallest) multiset<int> g; // Multiset s for storing lower half // (descending order). The first element // will be the largest multiset<int, greater<int> > s; s.insert(arr[0]); // Initialise median with the first element int med = arr[0]; printf("%d ", med); for (int i = 1; i < n; i++) { // Only add elements to upper half if // its size less than the size of the // lower half (maintain only difference // of 1) if (s.size() > g.size()) { if (arr[i] < med) { int temp = *s.begin(); s.erase(s.begin()); g.insert(temp); s.insert(arr[i]); } else g.insert(arr[i]); //median = top/begin of set with larger size = g.begin or s.begin med = *s.begin() > *g.begin() ? *g.begin() : *s.begin(); } // Only add elements to lower half if // it's size less than the size of the // upper half (maintain only difference // of 1) else if (s.size() < g.size()) { if (arr[i] > med) { int temp = *g.begin(); g.erase(g.begin()); s.insert(temp); g.insert(arr[i]); } else s.insert(arr[i]); //median = top/begin of set with larger size = g.begin or s.begin med = *s.begin() > *g.begin() ? *g.begin() : *s.begin(); } // If sizes are same else { if (arr[i] > med) { g.insert(arr[i]); //median = first element/begin of g med = *g.begin(); } else { s.insert(arr[i]); //median = first element/begin of s med = *s.begin(); } } printf("%d ", med); } printf("\n");}// Driver codeint main(){ int arr[] = { -10, 14, 11, -5, 7 }; int n = sizeof(arr) / sizeof(arr[0]); printRunningMedian(arr, n); return 0;} |
Python3
def printRunningMedian(arr): # Set g for storing upper half (ascending order) # The first element will be the smallest g = set() # Set s for storing lower half (descending order) # The first element will be the largest s = set() s.add(arr[0]) # Initialize median with the first element med = arr[0] print(med, end=" ") for i in range(1, len(arr)): # Only add elements to upper half if # its size less than the size of # the lower half (maintain only difference of 1) if len(s) > len(g): if arr[i] < med: temp = max(s) s.remove(temp) g.add(temp) s.add(arr[i]) else: g.add(arr[i]) # median = top/begin of set with larger size = g.begin or s.begin med = min(g) if max(s) > min(g) else max(s) # Only add elements to lower half if its size # less than the size of the upper half (maintain only difference of 1) elif len(s) < len(g): if arr[i] > med: temp = min(g) g.remove(temp) s.add(temp) g.add(arr[i]) else: s.add(arr[i]) # median = top/begin of set with larger size = g.begin or s.begin med = min(g) if max(s) > min(g) else max(s) # If sizes are same else: if arr[i] > med: g.add(arr[i]) # median = first element/begin of g med = min(g) else: s.add(arr[i]) # median = first element/begin of s med = max(s) print(med, end=" ")# Driver code to test above functionarr = [-10, 14, 11, -5, 7]printRunningMedian(arr) |
Java
import java.util.TreeSet;public class Solution { // Function to print the running median // for the array arr[] public static void printRunningMedian(int[] arr, int n) { // Multiset is used to handle duplicates // Multiset g for storing upper half // (ascending order) // The first element will be the smallest) TreeSet<Integer> g = new TreeSet<Integer>(); // Multiset s for storing lower half // (descending order). The first element // will be the largest TreeSet<Integer> s = new TreeSet<Integer>((a, b) -> (b - a)); s.add(arr[0]); // Initialise median with the first element int med = arr[0]; System.out.print(med + " "); for (int i = 1; i < n; i++) { // Only add elements to upper half if // its size less than the size of the // lower half (maintain only difference // of 1) if (s.size() > g.size()) { if (arr[i] < med) { int temp = s.first(); s.remove(s.first()); g.add(temp); s.add(arr[i]); } else { g.add(arr[i]); } //median = first element/begin of set with larger // size = g.first or s.first med = s.first() > g.first() ? g.first() : s.first(); } // Only add elements to lower half if // it's size less than the size of the // upper half (maintain only difference // of 1) else if (s.size() < g.size()) { if (arr[i] > med) { int temp = g.first(); g.remove(g.first()); s.add(temp); g.add(arr[i]); } else { s.add(arr[i]); } //median = first element/begin of set with //larger size = g.first or s.first med = s.first() > g.first() ? g.first() : s.first(); } // If sizes are same else { if (arr[i] > med) { g.add(arr[i]); //median = first element/begin of g med = g.first(); } else { s.add(arr[i]); //median = first element/begin of s med = s.first(); } } System.out.print(med + " "); } System.out.println(); } // Driver code public static void main(String[] args) { int[] arr = { -10, 14, 11, -5, 7 }; int n = arr.length; printRunningMedian(arr, n); }} |
C#
using System;using System.Collections.Generic;class GFG{ static void PrintRunningMedian(int[] arr, int n) { // Multiset is used to handle duplicates // Multiset g for storing upper half // (ascending order) // The first element will be the smallest) SortedSet<int> g = new SortedSet<int>(); // Multiset s for storing lower half // (descending order). The first element // will be the largest SortedSet<int> s = new SortedSet<int>(Comparer<int>.Create((a, b) => b.CompareTo(a))); s.Add(arr[0]); // Initialise median with the first element int med = arr[0]; Console.Write(med + " "); for (int i = 1; i < n; i++) { // Only add elements to upper half if // its size less than the size of the // lower half (maintain only difference // of 1) if (s.Count > g.Count) { if (arr[i] < med) { int temp = s.Min; s.Remove(temp); g.Add(temp); s.Add(arr[i]); } else { g.Add(arr[i]); } //median = top/begin of set with larger size = g.Min or s.Min med = s.Min > g.Min ? g.Min : s.Min; } // Only add elements to lower half if // it's size less than the size of the // upper half (maintain only difference // of 1) else if (s.Count < g.Count) { if (arr[i] > med) { int temp = g.Min; g.Remove(temp); s.Add(temp); g.Add(arr[i]); } else { s.Add(arr[i]); } //median = top/begin of set with larger size = g.Min or s.Min med = s.Min > g.Min ? g.Min : s.Min; } // If sizes are same else { if (arr[i] > med) { g.Add(arr[i]); //median = first element/begin of g med = g.Min; } else { s.Add(arr[i]); //median = first element/begin of s med = s.Min; } } Console.Write(med + " "); } Console.WriteLine(); } static void Main(string[] args) { int[] arr = { -10, 14, 11, -5, 7 }; int n = arr.Length; PrintRunningMedian(arr, n); }}// This code is contributed By Shivam Tiwari |
Javascript
function printRunningMedian(arr){ // Set g for storing upper half (ascending order) // The first element will be the smallest let g = new Set(); // Set s for storing lower half (descending order) // The first element will be the largest let s = new Set(); s.add(arr[0]); // Initialize median with the first element let med = arr[0]; process.stdout.write(med + " "); for (let i = 1; i < arr.length; i++) { // Only add elements to upper half if // its size less than the size of // the lower half (maintain only difference of 1) if (s.size > g.size) { if (arr[i] < med) { let temp = Math.max(...s); s.delete(temp); g.add(temp); s.add(arr[i]); } else { g.add(arr[i]); } // median = top/begin of set with larger size = g.begin or s.begin med = Math.max(...s) > Math.min(...g) ? Math.min(...g) : Math.max(...s); } // Only add elements to lower half if its size // less than the size of the upper half (maintain only difference of 1) else if (s.size < g.size) { if (arr[i] > med) { let temp = Math.min(...g); g.delete(temp); s.add(temp); g.add(arr[i]); } else { s.add(arr[i]); } // median = top/begin of set with larger size = g.begin or s.begin med = Math.max(...s) > Math.min(...g) ? Math.min(...g) : Math.max(...s); } // If sizes are same else { if (arr[i] > med) { g.add(arr[i]); // median = first element/begin of g med = Math.min(...g); } else { s.add(arr[i]); // median = first element/begin of s med = Math.max(...s); } } process.stdout.write(med + " "); }}// Driver codelet arr = [-10, 14, 11, -5, 7];printRunningMedian(arr); |
Output:
-10 -10 11 -5 7
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
