Discussion on Find the Running Median Challenge

Sort by

recency

|

256 Discussions

|

2 weeks ago+ 0 comments

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static class MinComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            if (i1 < i2) {
                return -1;
            } else if (i1 > i2) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static class MaxComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            if (i1 > i2) {
                return -1;
            } else if (i1 < i2) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        Queue<Integer> minHeap = new PriorityQueue<>(n/2+1, new MinComparator());
        Queue<Integer> maxHeap = new PriorityQueue<>(n/2+1, new MaxComparator());

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();

            if (!maxHeap.isEmpty() && num > maxHeap.peek()) {
                minHeap.offer(num);
            } else {
                maxHeap.offer(num);
            }

            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            } else if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            }

            double median = 0.0;
            if (minHeap.size() == maxHeap.size()) {
                median = 0.5 * (minHeap.peek() + maxHeap.peek());
            } else {
                median = (minHeap.size() > maxHeap.size()) ? minHeap.peek() : maxHeap.peek();
            }

            System.out.println(String.format("%1.1f", median));
        }
    }

}

4 weeks ago+ 0 comments

import math import os import random import re import sys

def runningMedian(a):

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

a_count = int(input().strip())

a = []

for _ in range(a_count):
    a_item = int(input().strip())
    a.append(a_item)

result = runningMedian(a)

fptr.write('\n'.join(map(str, result)))
fptr.write('\n')

fptr.close()

2 months ago+ 0 comments

import heapq

def runningMedian(a):
    maxh = []
    minh = []
    ans = []

    for aa in a:
        if len(maxh) == 0 or aa <= -maxh[0]:
            heapq.heappush(maxh, -aa)
        else:
            heapq.heappush(minh, aa)

        if len(maxh) > len(minh) + 1:
            heapq.heappush(minh, -heapq.heappop(maxh))
        elif len(minh) > len(maxh):
            heapq.heappush(maxh, -heapq.heappop(minh))

        if len(maxh) > len(minh):
            m = -maxh[0]
        else:
            m = (-maxh[0] + minh[0]) / 2
        ans.append(format(m, ".1f"))

    return ans

6 months ago+ 0 comments

I am surprised that I was able to get away with using a simple list structure (vector in C++). I started off with a simple, slow solution using std::sort, and then when that didn't pass, I made sure to insert each incoming int in the correct location. That was it. Not hard.

10 months ago+ 0 comments

Python3

import heapq import sys

def runningMedian(a):

lower_half = []   
upper_half = []   

result = []

for num in a:

    if len(lower_half) == 0 or num <= -lower_half[0]:
        heapq.heappush(lower_half, -num)  
    else:
        heapq.heappush(upper_half, num)


    if len(lower_half) > len(upper_half) + 1:
        moved_item = -heapq.heappop(lower_half)
        heapq.heappush(upper_half, moved_item)
    elif len(upper_half) > len(lower_half):
        moved_item = heapq.heappop(upper_half)
        heapq.heappush(lower_half, -moved_item)

    if len(lower_half) == len(upper_half):
        median = (-lower_half[0] + upper_half[0]) / 2.0
    else:
        median = -lower_half[0] / 1.0  


    result.append(format(median, ".1f"))

return result

if name == "main": input = sys.stdin.read().strip().split() n = int(input[0]) a = list(map(int, input[1:n+1])) medians = runningMedian(a) for median in medians: print(median)

Sort by

|

256 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge