Find-the-Running-Median/Solution.java

 import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'runningMedian' function below.

     *

     * The function is expected to return a DOUBLE_ARRAY.

     * The function accepts INTEGER_ARRAY a as parameter.

     */

    public static List<Double> runningMedian(List<Integer> a) {

    // Write your code here

        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());

        PriorityQueue<Integer> right = new PriorityQueue<>();

        List<Double> res = new ArrayList<>();

        for (int i = 0; i < a.size(); i++) {

            int tmp = a.get(i);

            left.add(tmp);

            if (left.size() - right.size() > 1) { right.add(left.poll()); }

            if (right.size() != 0 && left.peek() > right.peek()) {

                left.add(right.poll());

                right.add(left.poll());

            }

            double median;

            if (left.size() > right.size()) {

                median = 1.0 * left.peek();

            } else {

                median = (left.peek() + right.peek()) / 2.0;

            }

            res.add(median);

        }

        return res;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int aCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> a = IntStream.range(0, aCount).mapToObj(i -> {

            try {

                return bufferedReader.readLine().replaceAll("\\s+$", "");

            } catch (IOException ex) {

                throw new RuntimeException(ex);

            }

        })

            .map(String::trim)

            .map(Integer::parseInt)

            .collect(toList());

        List<Double> result = Result.runningMedian(a);

        bufferedWriter.write(

            result.stream()

                .map(Object::toString)

                .collect(joining("\n"))

            + "\n"

        );

        bufferedReader.close();

        bufferedWriter.close();

    }

}