## Sliding Window Maximum | Leetcode #239 This video explains a very important programming interview problem which is the sliding window maximum.I have explained and compared multiple techniques for this problem from bruteforce to heap and deque.In this problem, given an array and a window size, we are required to return an array of maximum elements for all the windows of given size.First I have explained the bruteforce or naive approach and then optimized the solution using heap data structure.Finally, I have shown the most optimal solution using deque.I have shown all the required intuition using examples.I have also shown CODE for all the explained techniques at the end of the video.

## CODE: MaxHeap

```//Max_Heap Solution
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//Pair<int,int> contains (nums[i],index)
priority_queue<pair<int,int>> heap; //Max_Heap to find maximum in a sliding window
vector<int> ans;    //Stores all maximum values for all sliding windows

for(int i=0;i<nums.size();++i)
{
while(!heap.empty() and heap.top().second<=(i-k))  //Pop the root (max_element),if it is out of sliding window
heap.pop();
heap.push(make_pair(nums[i],i));    //Push current element (along with its index) into the heap
if(i>=k-1)      //Store max in the window if we have a valid window (based on size K)
ans.push_back(heap.top().first);
}
return ans;
}
};```

## CODE: DeQue (Optimal)

```//DeQue Solution
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//Pair<int,int> contains (nums[i],index)
deque<pair<int,int>> dq;  //We will store elements in the deque only inside our current window
vector<int> ans;

for(int i=0;i<nums.size();++i)
{
if(!dq.empty() and dq.front().second<=(i-k))    //Remove front element if it goes out of window size
dq.pop_front();
while(!dq.empty() and dq.back().first<nums[i])  //Maintain elements in DSC order
dq.pop_back();
dq.push_back(make_pair(nums[i],i));     //Push current NODE
if(i>=(k-1))
ans.push_back(dq.front().first);    //Include maximum of cuurrent window
}
return ans;
}
};```