Problem Statement

Given an array of integers arr, 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.

Examples

Example 1:

Input: arr = [4, 0, -1, 3, 5, 3, 6, 8], k = 3
Output: [4, 3, 5, 5, 6, 8]

Explanation: 
Window position          Max
--------------------     -----

[4 0 -1] 3 5 3 6 8      4
 4 [0 -1 3] 5 3 6 8      3
 4 0 [-1 3 5] 3 6 8      5
 4 0 -1 [3 5 3] 6 8      5
 4 0 -1 3 [5 3 6] 8      6
 4 0 -1 3 5 [3 6 8]     8

For each window of size k=3, we find the maximum element in the window and add it to our output array.

Example 2:

Input: arr = [20, 25], k = 2
Output: [25]

Explanation: There’s just one window of size 2 that is possible and the maximum of the two elements is our answer.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A naive approach to solve this problem involves considering every window possible of size K and then finding the maximum element for each window.

Approach:

1. Traverse on the array getting all the windows possible of size K using a for loop.
2. For each window, find the maximum element using a nested for loop. Store the maximums obtained in a list.
3. Once the traversal for all the windows is complete, return the list as answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to get the maximum sliding window
    vector<int> maxSlidingWindow(vector<int> &arr, int k) {
        
        int n = arr.size(); // Size of array
        
        // To store the answer
        vector<int> ans;
        
        /* Traverse on the arrary 
        for valid window */
        for(int i=0; i <= n-k; i++) {
            
            // To store the maximum of the window
            int maxi = arr[i];
            
            // Traverse the window
            for(int j=i; j < i+k; j++) {
                // Update the maximum
                maxi = max(maxi, arr[j]);
            }
            
            // Add the maximum to the result
            ans.push_back(maxi);
        }
        
        // Return the stored result
        return ans;
    }
};

int main() {
    vector<int> arr = {4, 0, -1, 3, 5, 3, 6, 8};
    int k = 3;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    maximum sliding window */
    vector<int> ans = sol.maxSlidingWindow(arr, k);
    
    cout << "The maximum elements in the sliding window are: ";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O((N-K)*K) (where N is the size of given array)
  • Using two nested loops.
• Space Complexity:O(N-K)
  • Due to the size taken to return the answer.

2️⃣ Optimal Approach (Deque)

Intuition:

In the earlier approach, scanning every element of the window repeatedly was resulting in increased time complexity. Instead, if there can be a way where the maximum element for a window can be found in constant time, the overall time complexity will improve significantly.

What is the best suitable data structure?

Every time the sliding window moves by one step, an element is added to the window and an previously added element is removed from the window. A data-structure that can push elements from one end and remove elements from the other end is queue. Every time the window moves by one step, the queue is updated to manage the current window elements.

Understanding:

The maximum element in a particular window can be found directly using the concept of monotonic queue, which includes storing the elements in a decreasing order. This way the maximum element will always be the front element in the queue which can be retrieved from the queue in constant time.
In order to maintain the decreasing order of elements in queue, before adding the new element to the queue, all the smaller elements already present in front of the queue can be popped out.

But, a queue data structure does not provide pop operation from the front. To overcome this, a Deque (Double Ended Queue) can be used, which enables efficient insertion and retrieval from both ends.

Key Ideas:

• Use deque to store indices of elements.
• Remove all elements smaller than the current one (they are useless).
• Remove elements out of this window.
• The front of the deque is always the maximum.

Approach:

1. Determine the size of the input array. Prepare a vector to store the results. Utilize a deque to maintain the indices of array elements within the current window.
2. For each element in the array, update the deque to maintain only the indices of elements within the current window by popping the elements from the front.
3. Ensure the deque maintains a monotonic decreasing order by removing indices of elements from the back that are less than or equal to the current element. Add the current element's index to the back of the deque.
4. Once the first window(of required size) is fully traversed, store the maximum element (located at the front of the deque) for each window position by adding the corresponding array value to the result.
5. Return the result that contains the maximum values for each sliding window position and is returned as the output.

Code:

 #include <bits/stdc++.h>
using namespace std;

// Class to solve the sliding window maximum problem
class Solution {
public:
    // Function to return the maximum of each sliding window of size k
    vector<int> maxSlidingWindow(vector<int> &arr, int k) {
        
        int n = arr.size(); // Step 1: Get the size of the array
        
        vector<int> ans;    // Step 2: To store the final result (maximums)
        deque<int> dq;      // Step 3: A deque to store indices of useful elements
        
        // Step 4: Traverse each element in the array
        for (int i = 0; i < n; i++) {
            
            // Step 5: Remove elements that are out of the current window
            // i - k is the index just before the current window starts
            if (!dq.empty() && dq.front() <= (i - k)) {
                dq.pop_front();
            }
            
            // Step 6: Maintain elements in decreasing order in the deque
            // Remove all elements smaller than the current element from the back
            while (!dq.empty() && arr[dq.back()] <= arr[i]) {
                dq.pop_back();
            }
            
            // Step 7: Add the current element's index to the deque
            dq.push_back(i);
            
            // Step 8: If the window is fully formed, store the maximum (front of deque)
            if (i >= (k - 1)) {
                ans.push_back(arr[dq.front()]);
            }
        }
        
        // Step 9: Return the final list of maximums
        return ans;
    }
};

int main() {
    // Step 10: Input array and window size
    vector<int> arr = {4, 0, -1, 3, 5, 3, 6, 8};
    int k = 3;
    
    // Step 11: Create a Solution object
    Solution sol;
    
    // Step 12: Call the function to get sliding window maximums
    vector<int> ans = sol.maxSlidingWindow(arr, k);
    
    // Step 13: Print the result
    cout << "The maximum elements in the sliding window are: ";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the size of given array)
  • The array is traversed once taking O(N) time.
  • In the worst-case, each element is pushed in and popped out from deque only once taking O(N) time.
• Space Complexity:O(N-K) + O(K)
  • The deque will store K elements at maximum, taking O(K) time.
  • The result list stores N-K+1 maximums taking O(N-K) space.