Find the Running Median

Find the Running Median

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

public class Solution {

    /*
     * Complete the runningMedian function below.
     */
    static double[] runningMedian(int[] a) {
        /*
         * Write your code here.
         */

        
        double[] out = new double[a.length];
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });
        double median = 0;
        if(a.length == 1) {
            out[0] = a[0];
            return out;
        }
        for (int i = 0; i < a.length; i++) {
            if( i == 0) {
                out[0] = a[0];
            } else if (i == 1) {
                minHeap.add(Integer.max(a[0], a[1]));
                maxHeap.add(Integer.min(a[0], a[1]));
                out[i] = ((double) a[i - 1] + (double) a[i]) / 2;
                median = out[i];
            } else {
                       
                if(a[i] > median) {
                   minHeap.add(a[i]);
               } else if(a[i]<= median) {
                   maxHeap.add(a[i]);
               }
                
                if(Math.abs(minHeap.size() - maxHeap.size())>1) {
                    if(minHeap.size() > maxHeap.size())
                        maxHeap.add(minHeap.remove());
                    else minHeap.add(maxHeap.remove());
                }
                
                
                if(minHeap.size() == maxHeap.size())
                out[i] = ((double)minHeap.peek() + (double) maxHeap.peek())/2;
                else if (minHeap.size() > maxHeap.size())
                    out[i] = minHeap.peek().doubleValue();
                else if (maxHeap.size() > minHeap.size())
                    out[i] = maxHeap.peek().doubleValue();
                median = out[i];
                
            }
        }
        return out;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int aCount = Integer.parseInt(scanner.nextLine().trim());

        int[] a = new int[aCount];

        for (int aItr = 0; aItr < aCount; aItr++) {
            int aItem = Integer.parseInt(scanner.nextLine().trim());
            a[aItr] = aItem;
        }

        double[] result = runningMedian(a);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s