Algorithm


Problem Name: Data Structures - Find the Running Median

Problem Link: https://www.hackerrank.com/challenges/find-the-running-median/problem?isFullScreen=true

In this HackerRank in Data Structures - Find the Running Median solutions

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then:

  • If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set {1,2,3}, 2 is the median.
  • If your set contains an even number of elements, the median is the average of the two middle elements of the sorted sample. In the sorted set {1,2,3,4}, (2+3)/2 = 2.5 is the median.

Given an input stream of n integers, perform the following task for each i**th integer:

  1. Add the i**th integer to a running list of integers.
  2. Find the median of the updated list (i.e., for the first element through the i**th element).
  3. Print the updated median on a new line. The printed value must be a double-precision number scaled to 1 decimal place (i.e. 12.3 format).

Example

a = [7,3,5,2]

Sorted          Median
[7]             7.0
[3, 7]          5.0
[3, 5, 7]       5.0
[2, 3, 5, 7]    4.0

 

Each of the median values is stored in an array and the array is returned for the main function to print.

 

Note: Add formatting to the print statement.

 

Function Description
Complete the runningMedian function in the editor below.

 

runningMedian has the following parameters:
- int a[n]: an array of integers

 

Returns
- float[n]: the median of the array after each insertion, modify the print statement in main to get proper formatting.

Input Format

The first line contains a single integer, n the number of integers in the data stream.
Each line i of the n subsequent lines contains an integer, a[i] to be inserted into the list.

Constraints

  • 1 <= n <= 10**5
  • 0 <= a[i] <= 10**5

Sample Input

STDIN   Function
-----   --------
6       a[] size n = 6
12      a = [12, 4, 5, 3, 8, 7]
4
5
3
8
7

Sample Output

12.0
8.0
5.0
4.5
5.0
6.0

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct {
    int *array;
    int count;
    int size;
} Heap;

void heap_init(Heap *heap, int size) {
    heap->size = size;
    heap->array = (int *)malloc(size*sizeof(int));
    heap->count = 0;
}

void minheap_push(Heap *heap, int x) {
    assert(heap->count  <  heap->size);
    int i = heap->count;
    int p = (i-1)/2;
    while (i > 0 && x  <  heap->array[p]) {
        heap->array[i] = heap->array[p];
        i = p;
        p = (i-1)/2;
    }
    heap->array[i] = x;
    heap->count++;
}

void maxheap_push(Heap *heap, int x) {
    assert(heap->count  <  heap->size);
    int i = heap->count;
    int p = (i-1)/2;
    while (i > 0 && x > heap->array[p]) {
        heap->array[i] = heap->array[p];
        i = p;
        p = (i-1)/2;
    }
    heap -> array[i] = x;
    heap -> count++;
}

int minheap_pop(Heap *heap) {
    assert(heap->count > 0);
    int result = heap->array[0];
    int x = heap -> array[--heap -> count];
    int next, i = 0;
    while (1) {
        int left = 2*i + 1;
        int right = left + 1;
        if (left >= heap -> count) break;
        if (heap->array[left]  <  x) {
            if (right < heap->count && heap->array[right] < heap->array[left]) {
                next = right;
            } else {
                next = left;
            }
        } else if (right  <  heap -> count && heap -> array[right] < x) {
            next = right;
        } else {
            break;
        }
        heap->array[i] = heap->array[next];
        i = next;
    }
    heap->array[i] = x;
    return result;
}

int maxheap_pop(Heap *heap) {
    assert(heap->count > 0);
    int result = heap->array[0];
    int x = heap->array[--heap->count];
    int next, i = 0;
    while (1) {
        int left = 2*i + 1;
        int right = left + 1;
        if (left >= heap->count) break;
        if (heap->array[left] > x) {
            if (right  <  heap->count && heap->array[right] > heap->array[left]) {
                next = right;
            } else {
                next = left;
            }
        } else if (right  <  heap->count && heap->array[right] > x) {
            next = right;
        } else {
            break;
        }
        heap->array[i] = heap->array[next];
        i = next;
    }
    heap->array[i] = x;
    return result;
}


int main(void) {
    int n, x;
    scanf("%d", &n);
    
    int size = n/2 + 2;
    Heap minheap, maxheap;
    heap_init(&minheap, size);
    heap_init(&maxheap, size);
    
    for (int i = 0; i  <  n; i++) {
        scanf("%d", &x);

        // Decide which heap x should go on.
        if (minheap.count == 0) {
            minheap_push(&minheap, x);
        } else if (x > minheap.array[0]) {
            minheap_push(&minheap, x);
        } else {
            maxheap_push(&maxheap, x);
        }
        
        // Then adjust sizes of heaps until they differ by at most 1.
        while (minheap.count - maxheap.count > 1) {
            int x = minheap_pop(&minheap);
            maxheap_push(&maxheap, x);
        }
        while (maxheap.count - minheap.count > 1) {
            int x = maxheap_pop(&maxheap);
            minheap_push(&minheap, x);
        }

        float median;        
        if (minheap.count == maxheap.count) {
            median = 0.5*(minheap.array[0] + maxheap.array[0]);
        } else if (minheap.count > maxheap.count) {
            median = minheap.array[0];
        } else {
            median = maxheap.array[0];
        }
        printf("%.1f\n", median);
    }
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <set>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int N;
multiset < int> r;
multiset<int, greater<int> > l;
int main() {
    scanf("%d", &N);
    for (int i = 0; i  <  N; ++i) {
        int a; scanf("%d", &a);
        if (l.empty()) l.insert(a);
        else {
            if (a > *l.begin()) r.insert(a);
            else l.insert(a);
        }
        if (l.size() > r.size() + 1) {
            r.insert(*l.begin());
            l.erase(l.begin());
        } else if (r.size() > l.size()) {
            l.insert(*r.begin());
            r.erase(r.begin());
        }
        if (l.size() > r.size())
            printf("%d.0\n", *l.begin());
        else
            printf("%d.%c\n", (*l.begin() + *r.begin()) / 2, ((*l.begin() + *r.begin()) & 1) ? '5': '0');
    }
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
        	
        	int n = in.nextInt();
        	
        	PriorityQueue < Integer> minHeap = new PriorityQueue<>();
        	PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        	
        	for (int i = 0; i  <  n; ++i) {
        		int v = in.nextInt();
        		if (maxHeap.isEmpty() || (v  <  maxHeap.peek())) {
        			maxHeap.offer(v);
        		} else {
        			minHeap.offer(v);
        		}
        		
        		if (maxHeap.size() > (minHeap.size() + 1)) {
        			minHeap.offer(maxHeap.poll());
        		}
        		
        		if (minHeap.size() > (maxHeap.size() + 1)) {
        			maxHeap.offer(minHeap.poll());
        		}
        		
        		if (maxHeap.size() > minHeap.size()) {
        			System.out.println(maxHeap.peek());
        		} else if (minHeap.size() > maxHeap.size()) {
        			System.out.println(minHeap.peek());
        		} else {
        			System.out.println(0.5 * (minHeap.peek() + maxHeap.peek()));
        		}
        	}
        	
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


function processData(input) {
    //Enter your code here
      var inputArray = input.split('\n');
    var testCase = parseInt(inputArray[0]);
    var output=[], median=0;
 var minHeap = function(){
        this.myHeap = [];
        this.getSize = function(){
            return this.myHeap.length;
        };
        this.swap = function(i, j){             // swap;
            var temp;
            temp = this.myHeap[i];
            this.myHeap[i] = this.myHeap[j];
            this.myHeap[j] = temp;

        };
        this.bubble = function(i){
            var pi = Math.floor(i/2);  // parent's index
            if(this.myHeap[i] < this.myHeap[pi]){
                this.swap(i, pi);
                this.bubble(pi);
            }
        };
        this.bubble_down = function(i){
            var ci;
            if(i==0>{
                ci = (this.myHeap[1] > this.myHeap[2]) ? 2: 1;  // child index choose small one
            }else{
                ci = (this.myHeap[i*2] > this.myHeap[i*2 +1]) ? i*2+1: i*2;  // child index choose small one
            }


            if(this.myHeap[ci]<this.myHeap[i]){
                this.swap(ci, i);
                this.bubble_down(ci)
            }
        };
        this.addHeap = function(n){
            this.myHeap.push(n);
            this.bubble(this.myHeap.length-1);
        };
        this.peakMin = function(){
            return this.myHeap[0];
        }
        this.getMin = function(){
            this.swap(0, this.myHeap.length-1);
            var min= this.myHeap.pop();
            this.bubble_down(0);
            return min;
        }
    };
    var maxHeap = function(){
        this.myHeap = [];
        this.getSize = function(){
            return this.myHeap.length;
        };
        this.swap = function(i, j){             // swap;
            var temp;
            temp = this.myHeap[i];
            this.myHeap[i] = this.myHeap[j];
            this.myHeap[j] = temp;

        };
        this.bubble = function(i){
            var pi = Math.floor(i/2>;  // parent's index
            if(this.myHeap[i] > this.myHeap[pi]){
                this.swap(i, pi);
                this.bubble(pi);
            }
        };
        this.bubble_down = function(i){
            var ci;
            if(i===0){
                ci = (this.myHeap[1] < this.myHeap[2]) ? 2:1;
            }
            else{
                ci = (this.myHeap[i*2]  <  this.myHeap[i*2 +1]> ? i*2+1: i*2;  // child index choose big one
            }

            if(this.myHeap[ci]>this.myHeap[i]){
                this.swap(ci, i);
                this.bubble_down(ci)
            }
        };
        this.addHeap = function(n){
            this.myHeap.push(n);
            this.bubble(this.myHeap.length-1);
        };
        this.peakMax = function(){
            return this.myHeap[0];
        };
        this.getMax = function(){
            this.swap(0, this.myHeap.length-1);
            var max=this.myHeap.pop();
            this.bubble_down(0);
            return max;
        }
    };
    var minNode = new minHeap();           // keep it default -
    var maxNode = new maxHeap();
    var current,  smallmax, bigmin;
    current = parseInt(inputArray[1]);
    maxNode.addHeap(current);
    median = current;
    output.push(median.toFixed(1));
    for(var i=2; i<=testCase;i++) {
        current = parseInt(inputArray[i]);

        if( current  <  median ){
            //prev = maxNode.getMax();
            maxNode.addHeap(current);
            if (maxNode.getSize() == minNode.getSize()+1) {
                median = maxNode.peakMax();
            }else if (maxNode.getSize(> > minNode.getSize()+1) {
                smallmax = maxNode.getMax();
                minNode.addHeap(smallmax);
                bigmin = smallmax;
                smallmax= maxNode.peakMax();
                median = (bigmin + smallmax)/2;
            }
        }else{
            minNode.addHeap(current);
            if(maxNode.getSize() == minNode.getSize()) {
                median = ( maxNode.peakMax() + minNode.peakMin() ) / 2;
            }else if (maxNode.getSize() < minNode.getSize()) {
              bigmin= minNode.getMin();
                maxNode.addHeap(bigmin);
                median = bigmin;
            }
        }
         output.push(median.toFixed(1));
    }


    
    console.log(output.join('\n'));
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
}>;
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


from heapq import *
under = []
upper = []
N = int(input())
for _ in range(N):
    curNumber = int(input())
    if (len(upper) == 0):
        upper.append(curNumber)
        print(curNumber)
        continue
    middle = upper[0]
    if curNumber >= middle:
        heappush(upper,curNumber)
    else:
        heappush(under, -curNumber)
    if len(under) >= len(upper):
        heappush(upper, -heappop(under))
    if len(upper) >= len(under) + 2:
        heappush(under, -heappop(upper))
    if (len(upper) + len(under)) % 2 == 1:
        print(float(upper[0]))
    else:
        print((float(upper[0]) + -under[0])/2)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Kundu and Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Minimum Average Waiting Time solution in Hackerrank - Hacerrank solution C, C++, java,js, Python