[Geeks for Geeks] Maximum of all subarrays of size k

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/22/PS/GeeksforGeeks/maximum-of-all-subarrays-of-size-k/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.