480. Sliding Window Median

It is a hard level algorithm. I like to spend 30 minutes to work on the algorithm.

Sliding Window Median
C# using List.BinarySearch API practice in 2019

It is the hard level algorithm. I like to share my study code and talk about why it is hard for me to solve the algorithm.

I chose to study one of C# solutions, and then I put together the test case and figure out how it works.

Here are highlights:

1. Go through first k elements in the array and put into List by calling BinarySearch API to find index for next position; Therefore the list is sorted.
2. Once slide window size is k, remove left pointer, and then add median value into the list.
3. It is very good study code for me to learn how to build a sorted list using List API BinarySearch.

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

namespace _480_slide_window_median___study
{
    class Program
    {
        static void Main(string[] args)
        {
            var numbers = new int[]{1,3,-1,-3,5,3,6,7}; 
            var result = MedianSlidingWindow(numbers, 3);

            // result should be [1.0,-1.0,-1.0,3.0,5.0,6.0]
        }

        /// <summary>
        /// July 16, 2019
        /// study code:
        /// https://leetcode.com/problems/sliding-window-median/discuss/96357/C-BinarySearch-solution
        /// The idea is to insert the number into the index position found by binary search API.
        /// So the list is sorted in ascending order. 
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static double[] MedianSlidingWindow(int[] numbers, int k)
        {
            var list = new List<double>();

            if (numbers != null && numbers.Length > 0 && k > 0)
            {
                int half = (k >> 1);

                int median = half + (k & 1) - 1;

                var slideWindow = new List<double>();

                // slide window maintenance - put into window with sorted order first
                // remove left pointer value
                for (int i = 0; i < numbers.Length; ++i)
                {
                    if (i >= k)
                    {
                        slideWindow.Remove(numbers[i - k]);
                    }

                    int index = slideWindow.BinarySearch(numbers[i]);
                    if (index < 0)
                    {
                        index = ~index;
                    }

                    slideWindow.Insert(index, numbers[i]);

                    if (i >= k - 1)
                    {
                        list.Add(half == median ? slideWindow[half] : ((slideWindow[half] + slideWindow[median]) / 2));
                    }
                }
            }

            return list.ToArray<double>();
        }
    }
}