Leetcode 239 - sliding windows maximum - using binary search tree, C# class SortedSet, a hashtable

Leetcode239_slidingWindowMaximum_usingBST.cs

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

namespace Leetcode239_SlidingWindowMaximum_SortedSet
{
    /// <summary>
    /// code review on June 29, 2017
    /// SortedSet
    /// Leetcode 239 - https://leetcode.com/problems/Sliding-Window-Maximum/#/description
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase();
        }

        /*
         * 
         * [LeetCode Plus] Sliding Window Maximum
         * A long array A[] is given to you. There is a sliding window of size w which 
         * is moving from the very left of the array to the very right. You can only 
         * see the w numbers in the window. Each time the sliding window moves rightwards 
         * by one position. Following is an example: The array is [1, 3, -1, -3, 5, 3, 6, 7], 
         * and w is 3.
         * Window position                Max           Queue         Queue Mapped numbers
            ---------------               -----         ------        ----------------------
            [1  3  -1] -3  5  3  6  7       3           [1,2]         [1->3, 2->-1]
             1 [3  -1  -3] 5  3  6  7       3           [1,2,3]       [1->3, 2->-1, 3->-3]
             1  3 [-1  -3  5] 3  6  7       5           [4]           [4->5]
             1  3  -1 [-3  5  3] 6  7       5           [4, 5]        [4->5, 5->3]
             1  3  -1  -3 [5  3  6] 7       6           [6]           [6->6]
             1  3  -1  -3  5 [3  6  7]      7           [7]           [7->7]
         * 
         *  Input: A long array A[], and a window width w
            Output: An array B[], B[i] is the maximum value of from 
         *  A[i] to A[i + w - 1]
         */
        public static void RunTestcase()
        {
            var testcase = new int[] { 1, 3, -1, -3, 5, 3, 6, 7 };
            var maximums = MaxSlidingWindow(testcase, 3);
            Debug.Assert(maximums[0] == 3);
        }


        /// <summary>
        /// code review on June 29, 2017
        /// 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int[] MaxSlidingWindow(int[] nums, int k)
        {
            if (k < 1 || nums.Length == 0)
            {
                return new int[0];
            }

            var result = new int[nums.Length - k + 1];

            var map = new Dictionary<int, int>(nums.Length);

            var binarySearchTree = new SortedSet<int>();

            for (int i = 0; i < nums.Length; i++)
            {
                var visit = nums[i];

                binarySearchTree.Add(visit);   // O(LogK)

                map[visit] = i;       // O(1), duplicate number will be updated with latest index

                if (i < k - 1)
                {
                    continue;
                }

                if (i >= k && map[nums[i - k]] == (i - k))  // O(1)
                {
                    var kStepAway = nums[i - k];

                    binarySearchTree.Remove(kStepAway);    // O(logK)

                    map.Remove(kStepAway);        // O(1)
                }

                result[i - k + 1] = binarySearchTree.Max;    // O(1)
            }

            return result;
        }
    }
}