Sliding Window Maximum (Maximum of all subarrays of size k) (HELP)

Can anyone please help me to understand the Deque Approach of this problem as its not getting clear to me.

Basically here we trying to get maximum of all subaaray of size k in O(n) time.

in the Deque approach, we try to maintain a window of current k elements.
So for any ith elements, we have window [i-(k-1), i]
in this window, we keep only maximum elements that is the insight of this algorithm.

  so,
  1. If an element is in deque and it is out of i-(k-1), delete that element. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array

  2. Now only maximum elements are within [i-(k-1),i] are in the deque. We then pop elements smaller than a[i] from the tail. This is because if a[x] <a[i] and x<i, then a[x] has no chance to be the “max” in [i-(k-1),i], or any other subsequent window: a[i] would always be a better candidate.

  3. As a result elements in the deque are ordered in both sequence in an array and their value. At
    each step the head of the deque is the max element in [i-(k-1),i]

Hope you get the idea : )

code snippet
 deque<int>dq;
    vector<int>ans;
    int i;
    for(i=0;i<nums.size();i++){
        
       if(!dq.empty() && dq.front() == i-k)
        dq.pop_front();
        
        while(!dq.empty() && nums[dq.back()]<nums[i]) dq.pop_back();
        dq.push_back(i);
        if(i>=k-1)ans.push_back(nums[dq.front()]);
        
    }
    return ans;
3 Likes

https://www.techiedelight.com/Tags/sliding-window/ You can refer this site

2 Likes