Maximum of All Subarrays of Size K: Using Nested Loops
In this approach, we will be using nested loops. The maximum element in the window will be obtained by iterating from the i^{th} array index to the (i+k)^{th }array index.
Steps:
 Create a max variable.
 Iterate from starting index to n â€“ k^{th} elements in the outer loop.
 Iterate through the next k elements from the i^{th} element in the inner loop.
 Update the max value in the inner loop.

Print the maximum element of every window.
Code:
public class Main {
// function to calculate the maximum number in the subarray
private static void maxOfSubarray(int[] arr, int k) {
int max = Integer.MIN_VALUE;
// traverse from an index till the next k numbers
for(int i = 0 ; i <= arr.length  k ; i++) {
max = arr[i];
for(int j = i + 1 ; j <= i + k  1; j++) {
// find the maximum number
max = Math.max(max, arr[j]);
}
System.out.print(max+" ");
}
}
// driver Code
public static void main(String[] args) {
int[] arr = new int[] {11 ,3 ,9 ,6};
int k = 3;
maxOfSubarray(arr, k);
}
}
Output:
11 9
Complexity Analysis:

Time Complexity: O(n * k)
The outer loop runs for (nk+1) times, and the inner loop runs for k times. So the overall time complexity is O((nk+1)*k), which can be simplified to O(n * k).

Space Complexity: O(1) as no extra space is required.
Where "n" is the number of elements in the array, and "k" is the size of the window.
Read More  Time Complexity of Sorting Algorithms
Maximum of all subarrays of size k: Using Priority Queue
In this approach, we will use a priority queue that stores the elements in descending order of priority, i.e., the maximum element will have the highest priority. After every iteration, the priority queue will be updated with the latest elements.
Steps:
 Create a priority queue that stores the elements in descending order of priority.
 Add the first k numbers in the priority queue.
 Print the maximum element in the first subarray.
 Remove the first element from the priority queue.

Similarly, update the priority queue in every iteration and display the maximum element in each window.
Code:
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
// function to calculate the maximum number in the subarray
private static void maxOfSubarray(int[] arr, int k) {
// create a priority queue which stores the maximum element at the front end
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
int i;
// add first k numbers in the priority queue
for(i = 0 ; i < k ; i++)
priorityQueue.add(arr[i]);
// print the maximum number in the first subarray with size k
System.out.print(priorityQueue.peek()+" ");
// remove the first element from priority queue
priorityQueue.remove(arr[0]);
// add one element in every iteration and find the maximum element
for( ; i < arr.length ; i++) {
priorityQueue.add(arr[i]);
System.out.print(priorityQueue.peek()+" ");
priorityQueue.remove(arr[i  k + 1]);
}
}
// driver Code
public static void main(String[] args) {
int[] arr = new int[] {11 ,3 ,9 ,6};
int k = 3;
maxOfSubarray(arr, k);
}
}
Output:
11 9
Complexity Analysis:

Time Complexity: O(n * log k) as the elements are iterated once, and the insertion and deletion operations in the priority queue are O(log k).

Space Complexity: O(k) as the priority queue contains the "k" elements of the current window at any point in time.
Where "n" is the number of elements in the array, and "k" is the size of the window.
Maximum of all subarrays of size k: Using Deque
In this approach, we will use a deque that stores the array indexes. The queue is updated with the array indexes of "k" elements in every iteration by removing elements that are not there in the current window. The maximum element of every window is printed by accessing the element from the head of the deque.
Steps:
 Create a deque to store array indexes.
 Traverse the first k elements.
 While the deque is not empty, remove the smaller elements from the rear end as we need the maximum element. Else, add the elements into the deque.
 Traverse through the rest of the elements in the array.
 Print the maximum element of the previous window.
 Remove the elements that are not part of the current window.
 Then while the deque is not empty, remove the smaller elements from the rear end as we need the maximum element.
 Add the current element in the deque.

After completing the iteration, print the maximum element of the last window.
Code:
import java.util.Deque;
import java.util.LinkedList;
public class Main {
// function to calculate the maximum number in the subarray
private static void maxOfSubarray(int[] arr, int k) {
// create deque to store indexes of array elements
Deque<Integer> deque = new LinkedList<Integer>();
int i;
// traverse first k elements
for (i = 0; i < k; ++i) {
// remove the smaller elements from the rear end
while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) {
deque.removeLast();
}
// add current element at the rear end
deque.addLast(i);
}
// traverse through the rest of the elements
for (; i < arr.length; ++i) {
// print the maximum element of the previous window
System.out.print(arr[deque.peek()] + " ");
// remove elements that are not part of the current window
while ((!deque.isEmpty()) && deque.peek() <= i  k)
deque.removeFirst();
// remove the smaller elements from the rear end
while ((!deque.isEmpty()) && arr[i] >= arr[deque.peekLast()])
deque.removeLast();
// add current element at the rear end
deque.addLast(i);
}
// print the maximum element of last window
System.out.print(arr[deque.peek()]);
}
// driver Code
public static void main(String[] args) {
int[] arr = new int[] { 11, 3, 9, 6 };
int k = 3;
maxOfSubarray(arr, k);
}
}
Output:
11 9
Complexity Analysis:
 Time Complexity: O(n) as the elements are iterated once.

Space Complexity: O(k) as the deque contains the "k" elements of the current window at any point in time.
Where "n" is the number of elements in the array, and "k" is the size of the window.
Maximum of all subarrays of size k: Using Stacks
In this approach, we will use two stacks to store the elements. The k elements will be stored in both stack1 and stack2. The maximum element is found out by comparing the variable maximum of the topmost node in both stacks.
Steps:
 Create two stacks: stack1 and stack2.
 Add elements to stack2 except the last one in the first window.
 Traverse the array.
 Remove the element of the previous window if the loop counter is more than 1.
 Add the new element of the current window.
 Print the maximum element of the current window.
Note:
 The element is always added into stack2.

The element is always popped out from stack1. If stack1 is empty, push the elements of stack2 into stack1 and update the maximum variable accordingly. Then pop the element from stack1.
Code:
import java.util.Stack;
class Node {
int data;
int maximum;
}
public class Main {
// function to get the maximum element in the current window
private static int getMax(Stack<Node> stack1, Stack<Node> stack2) {
int max = Integer.MIN_VALUE;
// maximum element in stack1
if (stack1.size() > 0)
max = Math.max(max, stack1.peek().maximum);
// maximum element in stack2
if (stack2.size() > 0)
max = Math.max(max, stack2.peek().maximum);
return max;
}
// function to remove element present in the previous window
private static void deleteElement(Stack<Node> stack1, Stack<Node> stack2) {
// if stack1 is not empty remove the element of the previous window
if (stack1.size() > 0) {
stack1.pop();
} else {
// push all element from stack2 into stack1
while (!stack2.empty()) {
Node value = stack2.peek();
insertElement(stack1, value.data);
stack2.pop();
}
// remove the element of the previous window
stack1.pop();
}
}
// function to insertElement the new element present in the current window
private static void insertElement(Stack<Node> stack2, int value) {
// inserting the new element of the current window into stack2
Node newNode = new Node();
newNode.data = value;
if (stack2.empty()) {
newNode.maximum = value;
} else {
Node front = stack2.peek();
// initialize maximum of the node with the value of maximum element in current window
newNode.maximum = Math.max(value, front.maximum);
}
// push the new node to the stack
stack2.push(newNode);
}
// function to calculate the maximum number in the subarray
private static void maxOfSubarray(int[] arr, int k) {
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
// adding elements to stack2 except the last one in the first window
for (int i = 0; i < k  1; i++) {
insertElement(stack2, arr[i]);
}
for (int i = 0; i <= arr.length  k; i++) {
// remove the element of the previous window
if (i  1 >= 0) {
deleteElement(stack1, stack2);
}
// add new element of the current window
insertElement(stack2, arr[i + k  1]);
// print maximum element of the current window
System.out.print(getMax(stack1, stack2) + " ");
}
}
// driver Code
public static void main(String[] args) {
int[] arr = new int[] {11, 3, 9, 6};
int k = 3;
maxOfSubarray(arr, k);
}
}
Output:
11 9
Complexity Analysis:

Time Complexity: O(n) as the elements are iterated once, and the insertion and deletion operations of the stack are O(1).

Space Complexity: O(k) as at any point of time the sum of elements in both the stacks is "k."
Where "n" is the number of elements in the array, and "k" is the size of the window.
Maximum of all subarrays of size k: Using Self Balancing BST
In this approach, a selfbalancing Binary Search Tree (BST) is used. "k" elements are stored in the BST, and the maximum element is printed in every iteration.
Steps:
 Create a selfbalancing BST to store the "k" elements
 Traverse the array.
 Insert the element in the selfbalancing BST.
 When the window of size "k" is formed, the maximum element is printed, and the element from the previous window is deleted.
Code:
import java.util.TreeMap;
public class Main {
// function to remove the element of the previous window
private static void removeElement(TreeMap<Integer, Integer> treeMap, int value) {
treeMap.put(value, treeMap.getOrDefault(value, 0)  1);
// remove if no more element with the value is present
if (treeMap.get(value) == 0)
treeMap.remove(value);
}
// function to calculate the maximum number in the subarray
private static void maxOfSubarray(int[] arr, int k) {
// treemap stores the value of the element and the index
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for (int i = 0; i < arr.length; i++) {
// insert the new element of the current window
treeMap.put(arr[i], treeMap.getOrDefault(arr[i], 0) + 1);
// when the window size reaches the value of k
if (i + 1 >= k) {
// return max element in the current window
System.out.print(treeMap.lastKey() + " ");
// remove the element of the previous window
removeElement(treeMap, arr[i + 1  k]);
}
}
}
// driver Code
public static void main(String[] args) {
int[] arr = new int[] { 11, 3, 9, 6 };
int k = 3;
maxOfSubarray(arr, k);
}
}
Output:
11 9
Complexity Analysis:

Time Complexity: O(n * log k) as the elements are iterated once, and the operations of the BST of size "k" is O(log k).

Space Complexity: O(k) as at any point of time the treemap contains the "k" elements of the current window.
Where "n" is the number of elements in the array, and "k" is the size of the window.
Check this out: Array in Javascript
Frequently Asked Questions
What is the sliding window algorithm?
A window is a contiguous sequence part of a linear data structure like an array. The sliding window algorithm is an algorithm that grazes the window linearly over the array.
What is the advantage of using a BST?
BST has O(log n) time complexity for operations like lookup, insertion, and deletion, where n is the number of nodes in the tree.
What is a deque?
A deque is a doubleended queue where insert and delete operations are defined for the queue's front, and rear ends.
What is the time complexity to add and delete elements in a deque?
The time complexity to add and delete elements in a deque id O(1).
Conclusion
This blog covered the various methods to find the maximum of all subarrays of size k and their complexity analysis. The methods discussed are using a nested loop, priority queue, deque, stacks, and selfbalancing BST.
Recommended problems 
Don't stop here. Check out our Data Structures and Algorithmsguided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.