Leetcode discuss: 239. Sliding Window Maximum

Dec. 24, 2021

Here is the link. 

C# | Deque | Optimal time complexity O(N) | LinkedList API | Holiday rush

Dec. 24, 2021
Introduction
It is the day before 2021 Christmas day. I have to rush to warmup algorithms for Microsoft Vancouver code screen this Sunday. I chose to warmup this algorithm, since I came cross the algorithm. Double linkedList is a perfect choice to simulate a deque data structure. In order to get linear complexity to get maximum slide window, do not overdo. Three steps are my choices this time.

Deque | Slide window | C# LinkedList | Tips to share | Lessons learned | Warmup 30 minutes
I chose to write the code using C# and also tried to put together a test case to make sure that it runs perfectly.

I have not written very often C# code in my last two months, since I worked on system design. It is challenge to warm up, I manually walked through the test case, but I still came cross the following errors:

1. Missing one, if statement: if(i >= k - 1) <- case study: k = 3, i >= 2, not i >=3;
2. Index out of range, slideWindow[i - k + 1], after my first correction on step 1, I need to change the array's index;
3. Mix nums[index] with index. nums[LinkedList.First.Value] <- change it using nums[index]

Optimal time complexity O(N) | Maintain the window
It is important to come out linear solution, every index should get into deque exactly once, the deque should maintain index value of array, and those values of index matched should be in nonascending order, kind of monotonic pattern questions for quick prototype.

A simple test case to walk through | Powerful tool to reexamine the algorithm
Run a simple test case:
[1, 3, -1, -3], k = 3
Save index value of the array into slide window, maximum size is 3.
[0]
[1] -> remove 0 <- since nums[1] > nums[0]
[1, 2] -> slideWindow [3]
[1, 2, 3] -> slideWindow[3, 3]

The following C# code runs through Visual studio and the main function passes Leetcode online judge.

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

namespace _239_sliding_window_maximum
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = MaxSlidingWindow(new int[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3);
            // [3, 3, 5, 5, 6, 7]
            Debug.Assert(string.Join(",", result).CompareTo("3,3,5,5,6,7") == 0);  
        }

        /// <summary>
        /// Dec. 24, 2021
        /// 239. Sliding Window Maximum
        /// Using C# LinkedList to simulate a deque. The idea is to maintain a nonascending deque so that it is easy to get maximum one 
        /// and also using optimal time complexity O(N) to get maximum window. 
        /// The goal is to keep time complexity linear using deque data structure. 
        /// My warmup practice is to get more experience using C# LinkedList APIs. 
        /// Run a simple test case: 
        /// [1, 3, -1, -3], k = 3
        /// [0]
        /// [1] -> remove 0
        /// [1, 2] -> slideWindow [3]
        /// [1, 2, 3] -> slideWindow[3, 3]
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int[] MaxSlidingWindow(int[] nums, int k)
        {
            if(nums == null || nums.Length < k || k <= 0 )
                return new int[0];

            var linkedList = new LinkedList<int>(); // using index of the array
            var length = nums.Length; 
            var slideWindow = new int[length - k + 1];

            for (int i = 0; i < length; i++)
            {
                var value = nums[i];

                // case 1: remove the first one
                if (linkedList.Count > 0  && (i - linkedList.First.Value ) >= k)
                {
                    linkedList.RemoveFirst();
                }

                // add value to deque if needed
                while (linkedList.Count > 0 && nums[linkedList.Last.Value] < value)
                {
                    linkedList.RemoveLast();
                }

                // always
                linkedList.AddLast(i);

                // add value to slideWindow 
                if (i >= k - 1)
                {
                    slideWindow[i - k + 1] = nums[linkedList.First.Value]; 
                }
            }

            return slideWindow; 
        }
    }
}