https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?h_l=interview&isFullScreen=false&playlist_slugs%5B%5D%5B%5D%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D%5B%5D%5B%5D=sorting

FraudulentActivityNotifications.java

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

public class Solution {

    // Complete the activityNotifications function below.
    static int activityNotifications(int[] expenditure, int d) {
        // 15:00 THA 24/02/2019
        // by BingLi224
        // Reference: https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?h_l=interview&playlist_slugs%5B%5D%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D%5B%5D=sorting&isFullScreen=true
        int totalNotif = 0;
        int last = expenditure [ 0 ];
        int sz = expenditure.length;

        int [] expRange = new int [ d ];
        final int lastRange = d - 1;
        int idx = 0;
        while ( idx < d ) {
            expRange [ idx ] = expenditure [ idx ];
            idx ++;
        }
        Arrays.parallelSort ( expRange );

        boolean bEvenExp = ( d % 2 == 0 );
        int medianIdx = d / 2;
        // check for next one
        int day = d;
        while ( day < sz ) {
            int newExpend = expenditure [ day ];
            // find the median
            if ( bEvenExp ) {
                if ( ( expRange [ medianIdx ] + expRange [ medianIdx - 1 ] ) <= newExpend )
                    totalNotif ++;
            } else {
                if ( expRange [ medianIdx ] * 2 <= newExpend )
                    totalNotif ++;
            }

            day ++;
            if ( day >= sz )
                break;

            if ( last != newExpend ) {
                // replace expired with new expendit
                idx = medianIdx;
                int begin = 0;
                int end = d;
                while ( true ) {
                    if ( expRange [ idx ] == last ) {
                        if ( idx > 0 && newExpend < expRange [ idx - 1 ] ) {
                            do {
                                expRange [ idx ] = expRange [ idx - 1 ];
                                idx --;
                            } while ( idx > 0 && newExpend < expRange [ idx - 1 ] );
                        } else if ( idx < lastRange && newExpend > expRange [ idx + 1 ] ) {
                            do {
                                expRange [ idx ] = expRange [ idx + 1 ];
                                idx ++;
                            } while ( idx < lastRange && newExpend > expRange [ idx + 1 ] );
                        }
                        expRange [ idx ] = newExpend;
                        break;
                    } // not match
                    else if ( idx < end && expRange [ idx ] < last ) {
                        // go right
                        begin = idx + 1;
                        if ( begin >= end )
                            // not found???
                            throw new RuntimeException ( "Cannot found old expenditure: idx=" + idx + "[" + expenditure[idx] + "] newIdx=" + begin + " ending=" + end );
                        idx = begin + ( end - begin ) / 2;
                    } else {
                        // go left
                        end = idx;
                        if ( end <= begin )
                            //not found???
                            throw new RuntimeException ( "Cannot found old expenditure: idx=" + idx + "[" + expenditure[idx] + "] newIdx=" + end + " begin=" + begin );
                        idx = begin + ( end - begin ) / 2;
                    }
                } // while : replace the expired expendit
            } // if : old != new expenditure

            last = expenditure [ day - d ];
        }
        return totalNotif;
    }

    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")));

        String[] nd = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

        int[] expenditure = new int[n];

        String[] expenditureItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int expenditureItem = Integer.parseInt(expenditureItems[i]);
            expenditure[i] = expenditureItem;
        }

        int result = activityNotifications(expenditure, d);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}