Sliding Window Maximum hard

Problem Statement

Given an array of integers nums and an integer k, return the maximum value of each subarray of size k.

Example 1

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Example 2

Input: nums = [1], k = 1 Output: [1]

Steps

1. Initialization: Create a result list to store the maximum values for each window. Initialize a deque (double-ended queue) to store indices of elements. The deque will maintain the indices of elements in descending order of their values.

2. Sliding Window: Iterate through the nums array.

3. Deque Maintenance:

   • Remove elements from the rear of the deque: While the deque is not empty and the last element in the deque corresponds to a value smaller than or equal to the current element, remove it. This ensures that the deque always contains indices of elements in descending order.
   • Add the current element's index to the rear of the deque: This adds the current element's index to the deque maintaining the descending order property.

4. Window Size Check: If the current window size (index + 1) is greater than or equal to k:

   • Add the maximum value of the current window (the value at the front of the deque) to the result list.
   • Remove elements from the front of the deque: If the index of the element at the front of the deque is outside the current window, remove it.

5. Return Result: Return the result list.

Explanation

This solution uses a deque to efficiently track the maximum element within the sliding window. A deque is chosen because it allows for efficient addition and removal of elements from both ends (O(1) time complexity). The deque stores indices, not the values themselves. By maintaining the indices in descending order of their corresponding values, the maximum element within the window is always at the front of the deque. This avoids the need to iterate through the entire window to find the maximum, resulting in significant optimization.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.Length == 0 || k <= 0) {
            return new int[0];
        }

        List<int> result = new List<int>();
        Deque<int> deque = new Deque<int>(); //Using a custom Deque implementation (see below)

        for (int i = 0; i < nums.Length; i++) {
            // Remove elements smaller than the current element from the rear
            while (deque.Count > 0 && nums[deque.Last] <= nums[i]) {
                deque.RemoveLast();
            }
            // Add current element's index to the rear
            deque.AddLast(i);

            // Check if the window size is reached
            if (i >= k - 1) {
                // Add the maximum value to the result
                result.Add(nums[deque.First]);
                // Remove elements outside the window from the front
                if (deque.First == i - k + 1) {
                    deque.RemoveFirst();
                }
            }
        }

        return result.ToArray();
    }

    // Custom Deque Implementation (You can use a library like System.Collections.Generic.Queue)
    public class Deque<T>
    {
        private List<T> list;

        public Deque()
        {
            list = new List<T>();
        }

        public int Count { get { return list.Count; } }
        public T First { get { return list[0]; } }
        public T Last { get { return list[list.Count - 1]; } }

        public void AddFirst(T item) { list.Insert(0, item); }
        public void AddLast(T item) { list.Add(item); }
        public void RemoveFirst() { list.RemoveAt(0); }
        public void RemoveLast() { list.RemoveAt(list.Count - 1); }
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the input array. Each element is added and removed from the deque at most once.
• Space Complexity: O(k), where k is the size of the window. The deque can hold at most k elements.