Leetcode 239. Sliding Window Maximum | My discussion post

Aug. 31, 2021

Here is the link. 

C# | Deque | LinkedList class | LinkedListNode class | Descending order | Aug 2021

August 31, 2021
Introduction
I had a phone screen to work on LRU algorithm in 2020, and I chose to use C# class LinkedList. With 10 years experience, I could not explain what is return type of LinkedList First API. It is LinkedListNode. I could not write working code and ran it in the phone screen. Lessons learned, I like to write down and share with others.

Case study | How to solve it by hand? | Slide window
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
First visit, element value at index = 0, value = 1, which is current window's maximum value's index, put into C# LinkedList, [0]
Next visit, index = 1, value = 3, so argue that first element in the window will never be the maximum value, since 1< 3, remove 0 from LinkedList, call API RemoveFirst.
LinkedList - [1]
Next visit, index = 2, value = -1, so call LinkedList.AddLast,
LinkedList - [1, 2]
Next vist, index = 3, value = -3, call LinkedList.AddLast
LinkedList - [1, 2, 3]
Next visit, index = 4, value = 5, remove index = 3, 2, since all are impossible to be maximum value, 1 should be removed first since size should be less and equal to 3.

Code assessment practice | C# LinkedList | LinkedListNode | Study notes
I need to take some time to practice LinkedList API in C#, and get familiar with double linked list, and how it is designed in C#.

LinkedList C# Properties
Count, First, Last

LinkedList C# Methods
AddAfter, AddBefore, AddFirst, AddLast, Clear, Contains, CopyTo, Find, FindLast, GetEnumerator, Remove, RemoveFirst, RemoveLast

Time complexity O(N) | Deque data structure | Monotonic decreasing order in sliding window
Maintain the sliding window to keep the maximum value's index in the current window and all other possible index in future windows as well.

The following code passes online judge.

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k)
        {
            if (k == 0)
            {
                return nums;
            }

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

            var deque = new LinkedList<int>();

            // Queue stores indices of array, and 
            // values are in decreasing order (Argue why?)
            // So, the first node in queue should be the index value of the maximum number in window
            for (int index = 0; index < length; index++)
            {
                // 1. remove element from head until first number within window
                if (deque.Count > 0 && deque.First.Value + k <= index)
                {
                    deque.RemoveFirst();
                }

                // 2. before inserting i into deque, remove from the tail of the
                // queue indices with smaller value they array[i]
                while (deque.Count > 0 && nums[deque.Last.Value] <= nums[index])
                {
                    deque.RemoveLast();
                }

                deque.AddLast(index);

                // 3. set the max value in the window (always the top number in
                // queue)
                int maxPosition = index + 1 - k;
                if (maxPosition >= 0)
                {
                    result[maxPosition] = nums[deque.First.Value];
                }
            }

            return result;
        }
}