[Uber] Sliding Window Maximum

Problem: You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,2,3,1,4,5,2,7], k = 3
Output: [3,3,4,5,5,7]
Explanation: 
Sliding Window                 Max
---------------               -----
[1  2  3] 1  4  5  2  7         3
 1 [2  3  1] 4  5  2  7         3
 1  2 [3  1  4] 5  2  7         4
 1  2  3 [1  4  5] 2  7         5
 1  2  3  1 [4  5  2] 7         5
 1  2  3  1  4 [5  2  7]        7

Approach: Using Deque of size k. The idea is to store only potential elements of current window of size k. An element is potential if it is in current window and is greater than all other elements on right side of it in current window. In this way if we store elements in deque, we will ensure that the element at front of the deque is the largest and element at back of deque is the smallest of current window.

Here are the steps which we can follow:

1. Create a deque
2. Insert first k elements in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element, if it is so remove the element from the back of the deque, until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
3. Loop from k to n:
1. Add the front element of the deque to result.
2. Remove the element from the front of the queue if they are out of the current window.
3. Insert the next element in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element, if it is so remove the element from the back of the deque, until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
4. Add the front element of the deque to result to take care of last window.

Implementation in C#:

    public int[] MaxSlidingWindow(int[] nums, int k) 

   {

        if (nums == null)

        {

            return new int[] {};

        }

        if (k > nums.Length)

        {

            return new int[] {Enumerable.Max(nums)};

        }

        LinkedList<int> dequeue = new LinkedList<int>();

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

        for (int i = 0; i < k; ++i)

        {

            while (dequeue.Count > 0 && nums[i] >= nums[dequeue.Last.Value])

            {

                dequeue.RemoveLast();

            }

            dequeue.AddLast(i);

        }

        int writeIndex = 0;

        for (int i = k; i < nums.Length; ++i)

        {

            result[writeIndex++] = nums[dequeue.First.Value];

            while (dequeue.Count > 0 && i - dequeue.First.Value + 1 > k)

            {

                dequeue.RemoveFirst();

            }

            while (dequeue.Count > 0 && nums[i] >= nums[dequeue.Last.Value])

            {

                dequeue.RemoveLast();

            }

            dequeue.AddLast(i);

        }

        result[writeIndex] = nums[dequeue.First.Value];

        return result;

    }

Complexity: O(n), although it looked like more but if you look closely at max we are accessing the every element twice; adding and removing from queue.