Fraudulent Activity Notification - Openbracker code sprint - HackerRank - submission 2 - still timeout, spent hours to work on if/else, so many details.

fraudulentActivities_p2.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FraudulentActivityNotifications
{
    class Program
    {
        /*
         * https://www.hackerrank.com/contests/openbracket/challenges/fraudulent-activity-notifications
         * 7:45am
         * start to read the problem statement
         * 8:14am
         * To save time, store first d days expenditures into the array, 
         * sort the array. O(dlogd) time complexity
         * To iterate, how to use existing sorted result, remove first one 
         * in the array, and then, add a new one to the sorted result. 
         * 
         * Extra space - sort array -> LinkedList -> remove first one in the array, 
         * and then add one more in the LinkedList 
         * 
         * 8:25am start to write code
         * Write first version - be careful on time complexity
         * Avoid timeout issues
         * 
         * 
         * 12:25pm 
         * Find the bug
         * deadloop
         * write a test function using test case
         * 9 5
         * 2 3 4 2 3 6 8 4 5
         */
        static void Main(string[] args)
        {
            processing();
            //testing(); 
        }
        /*
         * test case: 
         *  * 9 5
         * 2 3 4 2 3 6 8 4 5
         */
        private static void testing()
        {
            int n = 9;
            int d = 5;
            string[] expenditures = "2 3 4 2 3 6 8 4 5".Split(' ');

            int result = calculateNotification(n, d, expenditures);
        }

        /*
         * standalone function:
         * 12:27am 
         */
        private static void processing()
        {
            string[] input = Console.ReadLine().Split(' ');
            int n = Convert.ToInt32(input[0]);
            int d = Convert.ToInt32(input[1]);

            string[] expenditures = Console.ReadLine().Split(' ');
            Console.WriteLine(calculateNotification(n, d, expenditures));
        }
        /*
         * start at 8:34am
         * 
         * 8:52am
         * http://stackoverflow.com/questions/2349589/is-this-a-good-way-to-iterate-through-a-net-linkedlist-and-remove-elements
         * 
         * 9:05am 
         * exit the function
         * Ready to do static analysis 
         * 9:11am
         * first execution on HackerRank
         * 9:18am
         * score 0 out of 20
         * pass test case #0 and #6, 
         * timeout on test case #1 - #5
         * 
         * 
         * Second trial: 
         * use binary search to speed up, O(logd) instead of linear search O(d)
         * work on code refactoring on 9:27am
         * 
         * copy existing array 
         * http://stackoverflow.com/questions/943635/getting-a-sub-array-from-an-existing-array
         * 
         * time complexity: 
         * set up the upper limit to (1)
         * http://stackoverflow.com/questions/21122143/what-is-the-time-complexity-for-copying-list-back-to-arrays-and-vice-versa-in-ja
         * LinkedList.ToArray() - C#, 
         * 
         * 10:11am 
         * start to review the code 
         * 
         * 10:24am
         * Bug to avoid:
         * Add position vs Remove position 
         * 
         * 10:40am
         * Java AddRange 
         * C# bulk copy 
         * http://stackoverflow.com/questions/9836471/why-is-addrange-faster-than-using-a-foreach-loop
         */
        private static int calculateNotification(
            int n,
            int d,
            string[] expenditures)
        {            
            int[] firstDDays = new int[d];
            for (int i = 0; i < d; i++)
                firstDDays[i] = Convert.ToInt32(expenditures[i]);

            Array.Sort(firstDDays);  

            int[] runner = new int[d];
            Array.Copy(firstDDays, runner, d); // O(n) 

            int count = 0;
            for (int i = d; i < n; i++)
            {
                int[] data = runner;  
                double medium = (d % 2 == 1) ?
                             data[d / 2] :
                             (data[d / 2 - 1] + data[d / 2]) / 2.0;

                int toAdd = Convert.ToInt32(expenditures[i]);

                if (toAdd >= 2 * medium)
                    count++;

                int inc = i - d;
                int toRemove = Convert.ToInt32(expenditures[0 + inc]);

                //int indexR = binarySearch(data, toRemove);
                //int indexAd = binarySearchAdd(data, toAdd);
                int indexR = 0;
                int indexAd = data.Length -1;

                runner = customizedArrayCopy(data, indexR, indexAd, toAdd, toRemove, d);
            }

            return count;
        }

        /*
         * start at 12:13pm 
         * search in a sorted array in ascending order
         * using binary search 
         * exit at 12:23pm 
         * 
         */
        private static int binarySearch(int[] data, int toFind)
        {
            int start = 0;
            int end = data.Length - 1;

            if (toFind < data[0] || toFind > data[end])
                return -1;

            while (start <= end)
            {
                int middle = start + (end - start) / 2;
                int compare = data[middle];

                if (compare < toFind)
                    start = middle;
                else if (compare > toFind)
                    end = middle;
                else
                    return middle;
            }

            return -1;
        }

        /*
         * 2 3 4 6 8
         * toFind is 5
         * need to return position: 3
         * 
         * Find position in sorted array to insert a new value, 
         * maintain the sorted order - ascending order after insertion. 
         * 
         */
        private static int binarySearchAdd(int[] data, int toFind)
        {
            int start = 0;
            int end = data.Length - 1;

            if (toFind < data[0] || toFind > data[end])
                return -1;

            while (end - start > 1)
            {                
                int middle = start + (end - start) / 2;
                int compare = data[middle];

                if (compare < toFind)
                    start = middle;
                else if (compare > toFind)
                    end = middle;
                else
                    return middle;
            }

            return end;
        }
        /*
         * start from 10:46am 
         * reference: 
         * http://stackoverflow.com/questions/9836471/why-is-addrange-faster-than-using-a-foreach-loop
         * 
         * bug to avoid: 
         * indexR vs indexAd 
         * 
         * if indexAd == -1, 
         * edge case, add one at the end of array; 
         * two sections 
         * 
         * otherwise, 
         * Arry will be divided into 3 section 
         * Section 0 /  section 1 / section 2
         * one more to add - can be 0 and 1, or 1 and 2
         * one more to remove - can be 0 and 1, or 1 and 2
         * 
         * Analyze if the function can be splitted into two: 
         * 
         * 11:16am 
         * still work on the coding 
         * 
         * 11:43am 
         * complete the first writing 
         * need to review the code 
         * 
         * 12:12pm 
         * end of reasoning, 
         * start to write the function 
         * binarySearch
         * 
         * 12:5pm
         * indexR = indexAd 
         * for test case: 
         * 9 5 
         * 2 3 4 2 3 6 8 4 5
         * last one, when i = 8
         * 
         * 1:20pm 
         * run time error 
         * need to work on this issue
         * 
         */
        private static int[] customizedArrayCopy(
            int[] data,
            int indexR,
            int indexAd,
            int toAdd,
            int toRemove,
            int size)
        {
            int[] data2 = new int[size];

            if (indexAd == -1)
            {
                bool isStart = toAdd < data[0];

                int start = 0;
                if (isStart)
                {
                    start = 1;
                    data2[0] = toAdd;
                }

                Array.Copy(data, 0, data2, 0 + start, indexR);

                int sourceIndex = indexR + 1;  // skip one element - data[indexR] 
                int destinationIndex = indexR + start;
                int length = size - sourceIndex;

                Array.Copy(data, sourceIndex, data2, destinationIndex, length);

                if (!isStart)
                    data2[size - 1] = toAdd;
            }
            else
            {
                bool removeFirst = indexR < indexAd;
                bool addFirst = indexAd > indexR;
                bool samePos = indexAd == indexR;

                int min = Math.Min(indexR, indexAd);
                int max = Math.Max(indexR, indexAd);

                Array.Copy(data, 0, data2, 0, min);

                if (removeFirst)
                {
                    int index1 = indexR;

                    // section 1 
                    int sourceIndex = index1 + 1;  // skip one element
                    int destinationIndex = index1;
                    int length = indexAd - sourceIndex;  // give me a reason why it is correct: two positions 
                    Array.Copy(data, sourceIndex, data2, destinationIndex, length);

                    // add position 
                    int addPos = indexAd - 1;  // adjust one, since one is removed; also, indexAd >=1, since indexAd > indexR
                    data2[addPos] = toAdd;

                    sourceIndex = addPos + 1;
                    destinationIndex = addPos;
                    length = size - sourceIndex;
                    Array.Copy(data, sourceIndex, data2, destinationIndex, length);
                }
                else if (addFirst) // add one element first
                {
                    int index1 = indexAd;

                    // add position                     
                    int addPos = indexAd;
                    data2[addPos] = toAdd;

                    // section 1 
                    int sourceIndex = index1;
                    int destinationIndex = index1 + 1;  // one is added
                    int length = indexR - sourceIndex;
                    Array.Copy(data, index1 + 1, data2, destinationIndex, length);

                    sourceIndex = indexR + 1;
                    destinationIndex = indexR;
                    length = size - sourceIndex;
                    Array.Copy(data, sourceIndex, data2, destinationIndex, length);
                }
                else
                {
                    data[indexR] = toAdd;
                    Array.Copy(data, 0, data2, 0, size);
                }
            }

            return data2;
        }
    }
}