Maximum of all subarrays of size k

Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.

• Time : O(nlogk)
• Space : O(k)

c++

class Solution
{
public:
    //Function to find maximum of each subarray of size k.
    vector <int> max_of_subarrays(int *arr, int n, int k)
    {
        if(n < k) return {};
        vector<int> res;
        priority_queue<int> window, remove;
        for(int i = 0; i <= k - 1; i++) window.push(arr[i]);
        res.push_back(window.top());
        for(int i = k; i < n; i++) {
            remove.push(arr[i-k]);
            window.push(arr[i]);
            while(!remove.empty() and remove.top() == window.top()) {
                window.pop();
                remove.pop();
            }
            res.push_back(window.top());
        }
        return res;
    }
};

• Time : O(n)
• Space : O(k)

c++

class Solution
{
public:
    //Function to find maximum of each subarray of size k.
    vector <int> max_of_subarrays(int *arr, int n, int k)
    {
        if(n < k) return {};
        vector<int> res;
        deque<int> dq;
        for(int i = 0; i <= k - 1; i++) {
            while(!dq.empty() and arr[dq.back()] <= arr[i]) dq.pop_back();
            dq.push_back(i);
        }
        res.push_back(arr[dq.front()]);
        for(int i = k; i < n; i++) {
            while(!dq.empty() and dq.front() <= i - k) dq.pop_front();
            while(!dq.empty() and arr[dq.back()] <= arr[i]) dq.pop_back();
            dq.push_back(i);
            res.push_back(arr[dq.front()]);
        }
        return res;
    }
};