Solution For Sliding Window Maximum

The problem “Sliding Window Maximum” on LeetCode asks us to find the maximum element in each sliding window of size k in an array of integers. To solve this problem, we can use a data structure called a deque.

A deque (short for double-ended queue) is a data structure that supports inserting and deleting elements from both ends in constant time. We can use a deque to keep track of the maximum element in the current sliding window. We will store the indices of the elements in the deque instead of the actual values, so we can efficiently remove elements that are outside of the current window.

Algorithm:

1. Initialize an empty deque.
2. Iterate through the first k elements of the array and add their indices to the deque in decreasing order of their values. We store indices instead of values to be able to remove elements that are outside the current window.
3. For each remaining element in the array, we remove elements from the deque that are outside the current window (i.e., their indices are less than i-k+1).
4. We then remove all elements from the deque that are smaller than the current element, as they cannot be the maximum element in the current window.
5. Add the index of the current element to the deque.
6. The maximum element in the current window is the first element in the deque.
7. Add the maximum element to the output array.
8. Return the output array.

Here is the Python code that implements this algorithm:

“`
from collections import deque

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
output = [] deque = deque()

    for i in range(k):
        while deque and nums[i] >= nums[deque[-1]]:
            deque.pop()
        deque.append(i)

    for i in range(k, len(nums)):
        output.append(nums[deque[0]])

        while deque and deque[0] <= i-k:
            deque.popleft()
        while deque and nums[i] >= nums[deque[-1]]:
            deque.pop()
        deque.append(i)

    output.append(nums[deque[0]])

    return output

“`

The time complexity of this algorithm is O(n), as each element is added and removed from the deque only once. The space complexity is O(k), as the deque stores at most k indices.

Step by Step Implementation For Sliding Window Maximum

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // base case
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        
        // create an array to store the maximum value of each window
        int[] maxValues = new int[nums.length - k + 1];
        
        // create a Deque to store the index of the elements
        // the Deque is used to keep track of the maximum value of each window
        // the front element of the Deque is the maximum value of the current window
        Deque deque = new ArrayDeque<>();
        
        // loop through the array
        for (int i = 0; i < nums.length; i++) {
            // if the Deque is not empty and the index of the element at the back of the Deque
            // is smaller than the current index, we can remove it since it will not be the 
            // maximum value of the current window or any future windows
            while (!deque.isEmpty() && deque.peekLast() < i) {
                deque.pollLast();
            }
            
            // if the Deque is not empty and the value of the element at the front of the Deque
            // is smaller than the current value, we can remove it since it will not be the 
            // maximum value of the current window or any future windows
            while (!deque.isEmpty() && nums[deque.peekFirst()] < nums[i]) {
                deque.pollFirst();
            }
            
            // add the current index to the Deque
            deque.offerFirst(i);
            
            // if the current index is greater than or equal to k - 1,
            // we can add the maximum value of the current window to the maxValues array
            if (i >= k - 1) {
                maxValues[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return maxValues;
    }
}

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return []
        
        # maintain a deque of size k
        dq = deque()
        res = []
        
        # process first k elements
        for i in range(k):
            # for every element, remove all elements from the 
            # deque that are smaller than the current element
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
                
            # add the current element at the end of the deque
            dq.append(i)
            
        # process rest of the elements
        for i in range(k, len(nums)):
            # append the maximum element from the previous window
            res.append(nums[dq[0]])
            
            # remove all elements from the deque that are 
            # smaller than or equal to the current element
            while dq and nums[i] >= nums[dq[-1]]:
                dq.pop()
                
            # remove the element from the front of the deque 
            # if it falls outside the current window
            if dq and dq[0] <= i - k:
                dq.popleft()
                
            # add the current element at the end of the deque
            dq.append(i)
            
        # append the maximum element from the last window
        res.append(nums[dq[0]])
        
        return res

var maxSlidingWindow = function(nums, k) {
    
    // create a results array
    // iterate through the nums array
        // for each iteration, add the max value of the current window to the results array
        // return the results array
    
    let results = [];
    
    for (let i = 0; i < nums.length - k + 1; i++) {
        let window = nums.slice(i, i + k);
        results.push(Math.max(...window));
    }
    
    return results;
};

The following is a C++ solution for the leetcode problem sliding-window-maximum:

vector maxSlidingWindow(vector& nums, int k) {
    deque dq;
    vector ans;
    for(int i=0;i=k-1)
            ans.push_back(nums[dq.front()]);
    }
    return ans;
}

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        // Base case: return empty array if nums is empty or k is 0
        if (nums.Length == 0 || k == 0) {
            return new int[0];
        }
        
        // Initialize result array with length = nums.Length - k + 1
        int[] result = new int[nums.Length - k + 1];
        
        // Initialize a deque to keep track of indices of elements in the current window
        // Deque will always contain indices in increasing order
        Deque deque = new Deque();
        
        // Iterate through nums
        for (int i = 0; i < nums.Length; i++) {
            // Add current element's index to the deque
            deque.AddLast(i);
            
            // Remove indices of elements that are not in the current window anymore
            // For example, if current element is at index 5 and k = 3, then we need to remove indices 0, 1, and 2 from the deque
            if (deque.First() <= i - k) {
                deque.RemoveFirst();
            }
            
            // Add the maximum element's index to the result array if we have reach the end of the current window
            // For example, if current element is at index 5 and k = 3, then the current window is [2, 3, 4, 5], and we can add index 4 to the result array
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.First()];
            }
        }
        
        return result;
    }
}