Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Maximum of all subarrays of size K: Problem Statement
3.
Maximum of All Subarrays of Size K: Using Nested Loops
4.
Maximum of all subarrays of size k: Using Priority Queue
5.
Maximum of all subarrays of size k: Using Deque
6.
Maximum of all subarrays of size k: Using Stacks
7.
Maximum of all subarrays of size k: Using Self Balancing BST
8.
Frequently Asked Questions
8.1.
What is the sliding window algorithm?
8.2.
What is the advantage of using a BST?
8.3.
What is a deque?
8.4.
What is the time complexity to add and delete elements in a deque?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Maximum of all Subarrays of Size K

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

A good programmer is the one who can write the most optimized codes. To develop this ability, the knowledge of data structures and algorithms becomes essential. Due to this reason, the knowledge of Data Structures and Algorithms (DSA) is frequently tested in interviews for SDE(Software Development Engineering) roles. The importance of DSA cannot be emphasized enough, especially if you aim to get placed in product-based companies like Google, Amazon, Microsoft, Adobe, etc.

For questions related to each data structure, refer to the blog Must-Do Coding Interview Questions for Product Based Companies.

This blog will discuss the interview problem: find the maximum of all subarrays of size k previously asked in companies like Amazon, SAP Labs, Flipkart, etc.

## Maximum of all subarrays of size K: Problem Statement

Given an array consisting of "n" non-negative integers and an integer "k" denoting the length of the subarray. Find the maximum element in each subarray of size k.

For example:-

Input:

``````arr: 11 3 6 9
k: 3``````

Output:

``11 9``

Explanation:

• Window 1: [11, 3, 6]

The maximum element is 11.

• Window 1: [3, 6, 9]

The maximum element is 9.

Explanation

Recommended: Please try to solve the "Maximum of all subarrays of size k" on "CODESTUDIO" first before moving on to the solution.

Now let's see various approaches to find the maximum of all subarrays of size k.
Maximum of all subarrays of size k: Using Nested Loops

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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 ith array index to the (i+k)th array index.

Steps:

1. Create a max variable.
2. Iterate from starting index to n â€“ kth elements in the outer loop.
3. Iterate through the next k elements from the ith element in the inner loop.
4. Update the max value in the inner loop.
5. 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 (n-k+1) times, and the inner loop runs for k times. So the overall time complexity is O((n-k+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:

1. Create a priority queue that stores the elements in descending order of priority.
2. Add the first k numbers in the priority queue.
3. Print the maximum element in the first subarray.
4. Remove the first element from the priority queue.
5. 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:

1. Create a deque to store array indexes.
2. Traverse the first k elements.
3. 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.
4. Traverse through the rest of the elements in the array.
5. Print the maximum element of the previous window.
6. Remove the elements that are not part of the current window.
7. Then while the deque is not empty, remove the smaller elements from the rear end as we need the maximum element.
8. Add the current element in the deque.
9. 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:

1. Create two stacks: stack1 and stack2.
2. Add elements to stack2 except the last one in the first window.
3. Traverse the array.
4. Remove the element of the previous window if the loop counter is more than 1.
5. Add the new element of the current window.
6. 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 self-balancing Binary Search Tree (BST) is used. "k" elements are stored in the BST, and the maximum element is printed in every iteration.

Steps:

1. Create a self-balancing BST to store the "k" elements
2. Traverse the array.
3. Insert the element in the self-balancing BST.
4. 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 double-ended 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 self-balancing BST.

Recommended problems -

Don't stop here. Check out our Data Structures and Algorithms-guided 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.

Live masterclass