Sliding Window Maximum

                                            
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;
        
        for (int i = 0; i < nums.size(); ++i) {
            while (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }
            
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            
            dq.push_back(i);
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        
        return result;
    }
};

                                            
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            if (i - k + 1 >= 0) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        from collections import deque
        if not nums:
            return []
        
        result = []
        window = deque()
        
        for i, num in enumerate(nums):
            while window and nums[window[-1]] < num:
                window.pop()
            
            window.append(i)
            
            if window[0] == i - k:
                window.popleft()
            
            if i >= k - 1:
                result.append(nums[window[0]])
        
        return result

To solve this coding challenge, we need to find the maximum value within a sliding window of size

k

that moves from the left to the right end of the array. We are provided with an array of integers

nums

and the window size

k

. Each time the window moves one position to the right, we need to capture the maximum value in the window and return a list of these maximum values.

# Explanation

Here, we’ll break down the solution and explain how to solve this challenge using a deque:

A deque (double-ended queue) will be used to store indices of the elements in
nums

. This helps efficiently track the maximum value in the current window because we can add and remove elements from both ends of the deque.
As we iterate over the array, we'll keep the deque in such a state that:

The elements' indices are in descending order based on their corresponding values in
nums

.
The left-most element in the deque is the index of the maximum element for the current window.

For each element, we:

Remove elements from the deque that are out of the current window’s range (i.e., their indices are less than the current index minus
k

).
Maintain the descending order in the deque by removing elements from the back of the deque as long as the current element is greater than the elements corresponding to those indices in the deque.
Add the current element's index to the deque.
If we have processed at least
k

elements, add the value of the element at the front of the deque to our results list.

Step-by-Step Explanation/Detailed Steps in Pseudocode:

Initialize the deque and the result list.
Iterate over each index and element in the array.
Adjust the deque by removing indices that are out of the current window.
Maintain the deque's descending order by removing smaller elements from the back.
Append the current index to the deque.
Once the first
k

elements have been processed, start adding the front element of the deque to the result list.

Pseudocode with Comments

                                            
# Initialize deque for storing indices and a list for result
result = []
window = deque()

# Iterate through the given nums list
for i = 0 to length(nums) - 1:
    # Remove elements from the back of the deque if they are smaller than current element
    while window is not empty and nums[window[-1]] < nums[i]:
        window.pop() # remove from back
    
    # Add current element index to the back of deque
    window.append(i)
    
    # Remove the front element if it is out of the current window
    if window[0] == i - k:
        window.popleft() # remove from front
    
    # Append result with the max value of the current window
    # window[0] is the index of the maximum element for the current window
    if i >= k - 1:
        result.append(nums[window[0]])

return result

In the above pseudocode:

window.pop()

removes the last element from the deque.
window.popleft()

removes the first element from the deque.
nums[window[0]]

gives the maximum element of the current window because the deque maintains elements' indices in descending order of their values in
nums

.

This detailed explanation and pseudocode should help in understanding and implementing the solution to the sliding window maximum problem effectively.