Max-Heap Approach
The approach of using a max heap to find the maximum of all subarrays involves maintaining a heap data structure where the maximum element in the current window of size k is always at the root of the heap. As the window slides through the array, we remove the elements that are no longer in the window and add the new elements that are now in the window. This approach ensures that we always have the maximum element readily available.
- Initialize an empty max heap.
- Iterate through the array from index 0 to n – 1, where n is the length of the array.
- For each element encountered, add it to the heap.
- If the size of the heap exceeds k, remove the element that is no longer in the window.
- If the size of the heap equals k, the maximum element in the current window is at the root of the heap. Add this maximum to the result array.
- Repeat steps 3 to 5 until all elements in the array are processed.
Example: To demonstrate maximizing all subarrays of size k using max-heap approach in JavaScript.
function maxSubArray(arr, k) {
const result = [];
const maxHeap = [];
for (let i = 0; i < arr.length; i++) {
maxHeap.push(arr[i]);
if (maxHeap.length > k) {
maxHeap.shift();
}
if (maxHeap.length === k) {
// Find the maximum value in the current
// window and add it to the result
result.push(Math.max(...maxHeap));
}
}
return result;
}
// Example usage:
const arr = [1, 3, 5, 2, 4, 6, 8];
const k = 3;
console.log(maxSubArray(arr, k));
Output
[ 5, 5, 5, 6, 8 ]
Time Complexity : O(n * log(k))
Auxiliary Space Complexity : O(k)
Maximum of all Subarrays of Size k using JavaScript
This problem is about finding the biggest number in all groups of k adjacent numbers in an array. In JavaScript, you’d go through the array, looking at each group of k numbers at a time, and picking out the biggest one. This task is pretty common and is useful for things like analyzing data or optimizing processes in JavaScript programming.
Input: Array[]= [1, 3, 5, 2, 4, 6, 8], K=3
Output: [5, 5,5,6, 8]
Explanation:
Subarray [1, 3, 5]: Maximum value is 5.
Subarray [3, 5, 2]: Maximum value is 5.
Subarray [5, 2, 4]: Maximum value is 5.
Subarray [2, 4, 6]: Maximum value is 6.
Subarray [4, 6, 8]: Maximum value is 8.
Below are the approaches to maximize all the subarrays of size K using JavaScript:
Table of Content
- Sliding Window Approach
- Max-Heap Approach
- Maximum of all subarrays of size K using Set