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;
    }
};