Median of Stream of Running Integers using STL | Set 2

0 0 5 minutes read

Given an array arr[] of size N representing integers required to be read as a data stream, the task is to calculate and print the median after reading every integer.

Examples:

Input: arr[] = { 5, 10, 15 } Output: 5 7.5 10 Explanation: After reading arr[0] from the data stream, the median is 5. After reading arr[1] from the data stream, the median is 7.5. After reading arr[2] from the data stream, the median is 10.

Input: arr[] = { 1, 2, 3, 4 } Output: 1 1.5 2 2.5

Approach: The problem can be solved using Ordered Set. Follow the steps below to solve the problem:

Initialize a multi Ordered Set say, mst to store the array elements in a sorted order.
Traverse the array using variable i. For every i^th element insert arr[i] into mst and check if the variable i is even or not. If found to be true then print the median using (*mst.find_by_order(i / 2)).
Otherwise, print the median by taking the average of (*mst.find_by_order(i / 2)) and (*mst.find_by_order((i + 1) / 2)).

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
typedef tree<int, null_type, 
less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> idxmst;
 
 
 
// Function to find the median
// of running integers
void findMedian(int arr[], int N)
{
    // Initialise a multi ordered set
    // to store the array elements 
    // in sorted order
    idxmst mst;
     
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Insert arr[i] into mst
        mst.insert(arr[i]);
 
        // If i is an odd number
        if (i % 2 != 0) {
 
            // Stores the first middle
            // element of mst
            double res 
             = *mst.find_by_order(i / 2);
 
            // Stores the second middle
            // element of mst
            double res1 
              = *mst.find_by_order(
                             (i + 1) / 2);
 
            cout<< (res + res1) / 2.0<<" ";
        }
        else {
 
            // Stores middle element of mst
            double res
               = *mst.find_by_order(i / 2);
 
            // Print median
            cout << res << " ";
        }
    }
}
 
// Driver Code
int main()
{
    // Given stream of integers
    int arr[] = { 1, 2, 3, 3, 4 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    findMedian(arr, N);
}

Python3

# Python program to implement the approach for finding the median of running integers
 
# Import the necessary module for Ordered Dict
from collections import OrderedDict
 
def find_median(arr):
  # Initialize an ordered dictionary to store the elements in sorted order
  ordered_dict = OrderedDict()
   
  # Traverse the array
  for i in range(len(arr)):
    # Insert arr[i] into ordered_dict
    ordered_dict[arr[i]] = ordered_dict.get(arr[i], 0) + 1
     
    # If i is an odd number
    if i % 2 != 0:
      # Find the middle elements and store them in a list
      mid = list(ordered_dict.keys())[i//2:i//2 + 2]
       
      # Calculate the median by taking the average of the middle elements
      median = (mid[0] + mid[1]) / 2
       
      # Print median
      print("%.1f" % median, end=" ")
    else:
      # Find the middle element
      mid = list(ordered_dict.keys())[i//2]
       
      # Print median
      print(mid, end=" ")
 
# Given stream of integers
arr = [1, 2, 3, 3, 4]
 
# Function call
find_median(arr)
# This code is contributed by Shivam Tiwari

Javascript

// JavaScript program to implement the approach for finding the median of running integers
 
// Initialize an object to store the elements in sorted order
let orderedObj = {};
 
function find_median(arr) {
  // Traverse the array
  for (let i = 0; i < arr.length; i++) {
    // Insert arr[i] into orderedObj
    orderedObj[arr[i]] = (orderedObj[arr[i]] || 0) + 1;
 
    // If i is an odd number
    if (i % 2 !== 0) {
      // Find the middle elements and store them in a list
      let mid = Object.keys(orderedObj).slice(i / 2, i / 2 + 2);
 
      // Calculate the median by taking the average of the middle elements
      let median = (parseInt(mid[0]) + parseInt(mid[1])) / 2;
 
      // Print median
      process.stdout.write(median.toFixed(1) + " ");
    } else {
      // Find the middle element
      let mid = Object.keys(orderedObj)[i / 2];
 
      // Print median
      process.stdout.write(mid + " ");
    }
  }
}
 
// Given stream of integers
let arr = [1, 2, 3, 3, 4];
 
// Function call
find_median(arr);
 
 
// This code is contributed by sdeadityasharma

Java

import java.util.*;
 
public class GFG {
 
    // Function to find the median
    // of running integers
    public static void findMedian(int[] arr) {
        // Initialize an ordered dictionary to store the elements in sorted order
        Map<Integer, Integer> ordered_dict = new TreeMap<>();
 
        // Traverse the array
        for (int i = 0; i < arr.length; i++) {
            // Insert arr[i] into ordered_dict
            ordered_dict.put(arr[i], ordered_dict.getOrDefault(arr[i], 0) + 1);
 
            // If i is an odd number
            if (i % 2 != 0) {
                // Find the middle elements and store them in a list
                List<Integer> mid = new ArrayList<>(ordered_dict.keySet()).subList(i / 2, i / 2 + 2);
 
                // Calculate the median by taking the average of the middle elements
                double median = (mid.get(0) + mid.get(1)) / 2.0;
 
                // Print median
                System.out.print(String.format("%.1f", median) + " ");
            } else {
                // Find the middle element
                int mid = new ArrayList<>(ordered_dict.keySet()).get(i / 2);
 
                // Print median
                System.out.print(mid + " ");
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args) {
        // Given stream of integers
        int[] arr = {1, 2, 3, 3, 4};
 
        // Function call
        findMedian(arr);
    }
}
// This code is contributed By Shivam Tiwari

C#

//C# program to implement the approach for finding the median of running integers
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        // Given stream of integers
        int[] arr = { 1, 2, 3, 3, 4 };
 
        // Function call
        find_median(arr);
    }
 
    // Function to find the median of running integers
    static void find_median(int[] arr)
    {
        // Initialize an ordered dictionary to store the elements in sorted order
        Dictionary<int, int> ordered_dict = new Dictionary<int, int>();
 
        // Traverse the array
        for (int i = 0; i < arr.Length; i++)
        {
            // Insert arr[i] into ordered_dict
            if (ordered_dict.ContainsKey(arr[i]))
            {
                ordered_dict[arr[i]]++;
            }
            else
            {
                ordered_dict[arr[i]] = 1;
            }
 
            // If i is an odd number
            if (i % 2 != 0)
            {
                // Find the middle elements and store them in a list
                var mid = ordered_dict.Keys.ToList().GetRange(i / 2, 2);
 
                // Calculate the median by taking the average of the middle elements
                var median = (mid[0] + mid[1]) / 2.0;
 
                // Print median
                Console.Write("{0:F1} ", median);
            }
            else
            {
                // Find the middle element
                var mid = ordered_dict.Keys.ToList().GetRange(i / 2, 1);
 
                // Print median
                Console.Write("{0} ", mid[0]);
            }
        }
 
         
    }
}
// This code is contributed by shivamsharma215

Output

1 1.5 2 2.5 3

Time Complexity: O(N * log(N))
Auxiliary Space: O(N)

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 zambiatek!