Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/find-the-running-median/problem?isFullScreen=true
In this HackerRank in Data Structures -
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:
- Add the i**th integer to a running list of integers.
- Find the median of the updated list (i.e., for the first element through the i**th element).
- 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;
}
#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;
}
#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()));
}
}
}
}
}
#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);
}>;
#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)