We will go through the major efficient approach for finding the maximum of all subarrays of size k in this article. All programmers must try to make their code more efficient and focus more on the time complexity of the method. Now, let us check the best approaches for finding the maximum of all subarrays of size K.
Problem Statement
An array of “n” non-negative integers and an integer “k” indicating the subarray length are provided to you. You need to identify the largest element in each size “k” subarray and then return an array containing those largest elements.
| Maximum of All Subarrays Of Size K |
| Input:
arr: 4 2 1 7 5 3 8 k: 4 Output: 7 7 7 8 Explanation: Window 1: [4, 2, 1, 7] The maximum element is 7. Window 2: [2, 1, 7, 5] The maximum element is 7. Window 3: [1, 7, 5, 3] The maximum element is 7. Window 4: [7, 5, 3, 8] The maximum element is 8. |
All you have to do is have an array of numbers and divide it into smaller subarrays of length k. For each subarray, you should find the largest number present in that subarray.
Finally, you must generate a new array containing the maximum values from each subarray and output that array.
Maximum Of All Subarrays Of Size K: Using Nested Loop
In this approach, we want to find the maximum element in each size K subarray within the given array. To do this, we use nested loops.
The subarray is formed by starting at the beginning of the array and traversing each element to its (i+k)th index. We locate the largest element within this subarray and print it. The process is repeated until the array’s end for all possible subarrays.
PseudoCode
Given here is the pseudocode for finding the intersection of the linked lists.
| Maximum of all Subarrays of size K: Using Loops |
| function maxOfSubarray(arr, k):
max = MIN_VALUE n = length of arr for i from 0 to (n – k): max = arr[i] for j from (i + 1) to (i + k – 1): max = max(max, arr[j]) print max main: arr = [11, 3, 9, 6] k = 3 maxOfSubarray(arr, k) |
The above pseudocode gives the approach to finding the maximum element in subarrays of size k with the help of a given array, let’s say “arr.”
- First, we will set the variable “max” to any minimal value.
- After that, we will use the outer loop to iterate through the array from index 0 to (n – k).
- We use an inner loop to find the maximum element in each subarray by setting “max” to the first element for each subarray.
- Finally, we print the largest element in each subarray.
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(n * k)
Space Complexity: O (1)
Maximum Of All Subarrays Of Size K: Using Deque
Here, we will use the deque method to find the maximum element in each size “k” subarray within the given array. We use a data structure called a deque, a double-ended queue. The deque stores the indexes of elements in the array.
- We start by traversing the first “k” elements in the deque.
- We also need to maintain the deque to ensure that it always contains the elements in decreasing order.
- The maximum element of each subarray can be obtained from the front of the deque.
- As we move forward in the array, we keep updating the deque by removing elements that are not part of the current window.
- We will add the current element in the correct position to maintain the decreasing order.
- The maximum element of each subarray is printed as we move through the array.
PseudoCode
Given here is the pseudocode for finding the intersection of the linked lists.
| Maximum of all Subarrays of size K: Using Deque |
| function maxOfSubarray(arr, k):
// Create a deque to store indexes of array elements deque = empty deque // Traverse the first k elements for i from 0 to (k-1): // Remove the smaller elements from the rear end while deque is not empty and arr[i] >= arr[deque.back()]: deque.removeLast() // Add the current element at the rear end deque.addLast(i) // Traverse through the rest of the elements for i from k to (n-1): // Print the maximum element of the previous window print arr[deque.front()] + ” “ // Remove elements not part of the current window while deque is not empty and deque.front() <= (i – k): deque.removeFirst() // Remove the smaller elements from the rear end while deque is not empty and arr[i] >= arr[deque.back()]: deque.removeLast() // Add the current element at the rear end deque.addLast(i) // Print the maximum element of the last window print arr[deque.front()] |
The above pseudocode outlines the steps to find the maximum element in each size “k” subarray within the given array “arr” using a deque.
- We start by initializing an empty deque.
- Then, we traverse the array’s first “k” elements and maintain the deque in decreasing order.
- As we proceed through the array, we update the deque by removing components that are not part of the current window and adding the current component in the proper place
- Finally, as we traverse the array, we print the largest element of each subarray.
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(n)
Space Complexity: O (k)
Recommended Technical Course
- Full Stack Web Development Course
- Generative AI Course
- DSA C++ Course
- Java+DSA 1.0 Course
- Data Analytics Course
- Data Science with ML 1.0 Course
Maximum Of All Subarrays Of Size K: Using Stack
The approach of this method is to identify the largest element in each subarray of size “k” of the given array. Two stacks are used to manage the elements in the active window to achieve this.
While the second stack keeps track of the maximum element in each window, the first stack stores the elements of the currently open window.
As we move through each window of the array, elements are added to and taken away from both stacks. The top elements of both stacks can be compared to determine the maximum element in each window.
PseudoCode
Given here is the pseudocode for finding the Maximum of all subarrays of size K using stack.
| Maximum of all Subarrays of size K: Using Stack |
| function getMax(stack1, stack2):
max = MIN_VALUE if stack1 is not empty: max = max(max, stack1.top().maximum) if stack2 is not empty: max = max(max, stack2.top().maximum) return max function deleteElement(stack1, stack2): if stack1 is not empty: stack1.pop() else: while stack2 is not empty: value = stack2.top() insertElement(stack1, value.data) stack2.pop() stack1.pop() function insertElement(stack2, value): newNode = new Node() newNode.data = value if stack2 is empty: newNode.maximum = value else: front = stack2.top() newNode.maximum = max(value, front.maximum) stack2.push(newNode) function maxOfSubarray(arr, k): stack1 = empty stack stack2 = empty stack for i from 0 to (k-1): insertElement(stack2, arr[i]) for i from 0 to (n-k): if i-1 >= 0: deleteElement(stack1, stack2) insertElement(stack2, arr[i + k – 1]) print getMax(stack1, stack2) + ” “ |
Let us check the stepwise breakdown of the stack approach.
- At first, we need to create two stacks, say stack1 and stack2, to store elements.
- Add all elements to stack2 except the last one in the first window.
- Beginning with the first window, we traverse the array and add each element to stack2 except for the final one.
- The element from the previous window is taken out of either stack1 or stack2, depending on which one is not empty, as we move on to the next window.
- Now, add the new element of the current window to stack2.
- At last, you need to find the maximum element by comparing the top elements of stack1 and stack2 and then print that maximum element.
Also read: Analysis of Algorithm in Data Structure
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(n)
Space Complexity: O (k)
Maximum Of All Subarrays Of Size K: Using Priority Queue
In this method, the largest number in each group of “k” consecutive numbers in the given array is determined using a data structure called a priority queue. The largest number always comes first in the priority queue because of how it organizes the numbers.
The first “k” numbers from the array are continuously added to the priority queue, which is then updated with the largest number (maximum element) from that group as we move through the array.
PseudoCode
Given here is the pseudocode for finding the Maximum of all subarrays of size K using Priority queue.
| Maximum of all Subarrays of size K: Using Priority Queue |
| function maxOfSubarray(arr, k):
// create a priority queue that stores the maximum element at the front end priority queue = empty priority queue //Add first k numbers in the priority queue for i from 0 to (k-1): priorityQueue.add(arr[i]) // print the maximum number in the first subarray with size k 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 from k to (n-1): priorityQueue.add(arr[i]) print priorityQueue.peek() + ” “ priorityQueue.remove(arr[i – k + 1]). |
Let us check the stepwise breakdown of the priority queue approach.
- Make a special container called a priority queue, where items are arranged in descending priority, with the largest item having the highest priority.
- Initially, add the first “k” numbers from the array into the priority queue.
- The largest element in the first subarray of “k” numbers should be located and printed from the first subarray.
- To start filling the next subarray, remove the first element from the priority queue.
- Now, repeat the following steps for each following subarray.
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(n*logk)
Space Complexity: O (k)
Also Read Technical Topics
FAQs
What is the sliding window algorithm?
The sliding window algorithm is a method used in computer programming to process a window or a fixed-size subarray that moves linearly over the elements of an array. It is beneficial for effectively resolving issues involving substring manipulation.
What is the advantage of using a Binary Search Tree (BST)?
Binary Search Trees are very efficient data structures and have an efficient time complexity generally in the order of O(logn) for essential operations.
Can a priority queue find the maximum element in each subarray?
We can use a priority queue to find the minimum element in each subarray. By using a priority queue with elements arranged in descending order.
How does the deque approach helps to find the maximum element in size K subarrays?
The deque approach keeps the maximum number of elements in each subarray by using a double-ended queue. The maximum element is always at the front thanks to the efficient updating of the deque while iterating through the array. This approach has a time complexity of O(n).
