Understanding the Problem:

You're given an array of integers, nums, and a sliding window of size k that moves from the very left of the array to the very right. At each step, you can only see the k numbers within the window. The window slides one position to the right each time.

Your Task:
Return an array containing the maximum value in each sliding window.

didn't get it ? ! No Problem dosthh ! lets deep dive 

Imagine you're driving along a straight road with gas stations (think of them as positions in the array). You have a window (of size k) that shows a fixed number of gas stations at a time. As you move forward (slide the window), you want to know the maximum gas available in your current view.

But instead of gas, we're dealing with numbers, and we want to find the maximum number within each window as it slides through the array.

Naive Approach: The Double Loop 🌀

Logic:

The simplest way to solve this problem is to:

1. Iterate through the array with a loop.
2. For each position, extract the current window of size k.
3. Find the maximum in this window.
4. Store the maximum in a result array.
5. Repeat until the window has slid through the entire array.

Code Implementation:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        int n = nums.size();
        
        for(int i = 0; i <= n - k; ++i){
            // Extract the window
            vector<int> window(nums.begin() + i, nums.begin() + i + k);
            // Find the maximum in the window
            int max_val = *max_element(window.begin(), window.end());
            // Store it
            result.push_back(max_val);
        }
        
        return result;
    }
};

Pros using this Approch ! :

• Simple to understand and implement.

Cons(dis-advantages) :

• Inefficient for large datasets.

• Time Complexity: $O(n\times k)$

  For each of the $n-k+1$ windows, you're performing a kkk-length scan to find the maximum.

Why We Need a Better Approach:

Given the constraints (especially nums.length up to 10^5),

the naive approach becomes too slow. We need something more efficient—preferably O(n) time complexity.

Optimal Approach: Using a Deque 🕶️

Intuition:

To achieve O(n) time complexity, we need a way to:

• Find the maximum in each window efficiently.
• Avoid redundant comparisons.

A deque (double-ended queue) is perfect for this. Here's why:

1. Maintain Order: We can keep track of potential maximum candidates in a way that the largest element is always at the front.
2. Efficiently Add/Remove Elements: We can add or remove elements from both ends in constant time.

How It Works:

1. Initialize a deque to store indices of elements. The deque will store indices in decreasing order of their corresponding values in nums.
2. Iterate through the array:
   • Remove indices from the back of the deque if the current element is greater than or equal to the elements corresponding to those indices. They can't be the maximum if the current element is larger.
   • Add the current index to the back of the deque.
   • Remove the front index if it's outside the current window (i - k + 1).
   • The front of the deque now contains the index of the maximum element for the current window.
3. Store the maximum for each window in the result array.

Visualization:

Let's walk through Example 1 to visualize the process.

Example 1:

• Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
• Output: [3,3,5,5,6,7]

Step-by-Step Walkthrough:

Explanation:

1. Indices 0 to 2:

   • Build the initial window [1,3,-1].
   • Deque maintains indices [1,2] because 3 (index 1) is larger than 1,                                   and -1 (index 2) is less than 3.
   • Maximum is 3.

2. Index 3:

   • Slide the window to [3,-1,-3].
   • -3 is added; deque becomes [1,2,3].
   • Maximum remains 3 (index 1).

3. Index 4:

   • Slide the window to [-1,-3,5].
   • Remove indices 1, 2, and 3 as 5 is larger.
   • Deque becomes [4].
   • Maximum is 5.

4. Index 5:

   • Slide the window to [-3,5,3].
   • Add index 5; deque becomes [4,5].
   • Maximum remains 5 (index 4).

5. Index 6:

   • Slide the window to [5,3,6].
   • Remove index 5 because 6 is larger.
   • Deque becomes [4,6].
   • Maximum is 6.

6. Index 7:

   • Slide the window to [3,6,7].
   • Remove index 4 because 7 is larger.
   • Deque becomes [7].
   • Maximum is 7.

Code Walkthrough:

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq; // Stores indices
        vector<int> ans; // Stores the maximums

        // Process the first 'k' elements
        for (int i = 0; i < k; i++) {
            // Remove elements from the back that 
            // are smaller than the current element
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            // Add current index to the back
            dq.push_back(i);
        }

        // The front of the deque has the index of the
        //  largest element for the first window
        ans.push_back(nums[dq.front()]);

        // Process the remaining elements
        for (int i = k; i < nums.size(); i++) {
            // Remove the front element if it's outside the current window
            if (!dq.empty() && i - dq.front() >= k) {
                dq.pop_front();
            }

            // Remove elements from the back that are smaller
            // than the current element
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }

            // Add current index to the back
            dq.push_back(i);

            // The front of the deque has the index of the 
           // largest element for the current window
            ans.push_back(nums[dq.front()]);
        }

        return ans;
    }
};

Didn't Understand ? Lets go Step-by-Step :

1. Initialize a Deque and Result Vector:

   • deque<int> dq;
     • Stores indices of potential maximum elements in the current window.
   • vector<int> ans;
     • Stores the maximums for each window.

2. Process the First Window (First 'k' Elements):

for (int i = 0; i < k; i++) {
    while (!dq.empty() && nums[i] >= nums[dq.back()]) {
        dq.pop_back();
    }
    dq.push_back(i);
}

• Purpose:
  Populate the deque with indices from the first window while maintaining decreasing order of their corresponding nums values.
• How:
  • Compare Current Element (nums[i]) with the Last Element in Deque (nums[dq.back()]):
    If nums[i] is greater or equal, pop the last index since nums[i] could be a potential maximum for future windows.
  • Add Current Index to the Deque:
    This ensures that the deque contains indices of elements in decreasing order.

   3.Add Maximum of First Window to Result:

ans.push_back(nums[dq.front()]);

Why ! The Reason ! ? :
Because ! The front of the deque (dq.front()) holds the index of the maximum element for the first window.

 3.Process the Remaining Elements:

for (int i = k; i < nums.size(); i++) {
    // Remove indices outside the current window
    if (!dq.empty() && i - dq.front() >= k) {
        dq.pop_front();
    }

    // Remove elements smaller than the current element from the back
    while (!dq.empty() && nums[i] >= nums[dq.back()]) {
        dq.pop_back();
    }

    // Add current index to the deque
    dq.push_back(i);

    // Add the current maximum to the result
    ans.push_back(nums[dq.front()]);
}

Steps Happening in this code block ! :

1. Remove Out-of-Window Indices:
   • If the index at the front of the deque is no longer within the current window, remove it.
2. Maintain Decreasing Order in Deque:
   • Remove all indices from the back whose corresponding nums values are less than or equal to nums[i].
3. Add Current Index to Deque:
   • Ensures the deque has potential candidates for the maximum.
4. Add Current Maximum to Result:
   • The front of the deque always holds the index of the maximum element for the current window.

---------------------------------------------------------------------------------------------------------------------------------------------

Why This Works:

• Monotonic Deque:
  The deque maintains indices in a monotonically decreasing order of their corresponding nums values. This means:

  • The front always has the index of the current maximum.
  • Any index whose corresponding value is less than the current element (nums[i]) is removed because it cannot be the maximum in the presence of a larger element.

• Efficiency:

  • Each element is added and removed at most once, ensuring linear time complexity.

Time and Space Complexity:

• Time Complexity: O(n)
  • Each element is processed exactly once.
• Space Complexity: O(k)
  • The deque holds at most k elements.

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq; // Stores indices of potential max elements
        vector<int> ans; // Stores the maximums

        // Process the first window
        for (int i = 0; i < k; i++) {
            // Remove smaller elements from the deque
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            // Add current element's index
            dq.push_back(i);
        }

        // Add the max of the first window
        ans.push_back(nums[dq.front()]);

        // Process the rest of the array
        for (int i = k; i < nums.size(); i++) {
            // Remove indices outside the current window
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            // Remove smaller elements from the deque
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }

            // Add current element's index
            dq.push_back(i);

            // Add the current max to the result
            ans.push_back(nums[dq.front()]);
        }

        return ans;
    }
};

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3