Sliding Window Approach
- Start by initializing two pointers, let’s call them ‘left’ and ‘right’, both pointing to the beginning of the array.
- Move the ‘right’ pointer to the right until the size of the window (distance between ‘left’ and ‘right’ pointers) becomes k.
- At each step, keep track of the maximum value within the current window.
- Once the window size reaches k, record the maximum value.
- Move the window by incrementing the ‘left’ pointer and ‘right’ pointer simultaneously.
- Repeat steps 2-5 until the ‘right’ pointer reaches the end of the array.
- Return the recorded maximum values for each window.
Example: To demonstrate maximizing all the sub arrays of size k using the sliding window approach in JavaScript.
function maxSubarrays(arr, k) {
const result = [];
const window = [];
const addElement = (index) => {
while (window
.length > 0 && arr[index] >= arr[window[window.length - 1]]) {
window.pop();
}
window.push(index);
};
const removeElement = (index) => {
if (window.length > 0 && window[0] === index) {
window.shift();
}
};
for (let i = 0; i < k; i++) {
addElement(i);
}
for (let i = k; i < arr.length; i++) {
result.push(arr[window[0]]);
removeElement(i - k);
addElement(i);
}
result.push(arr[window[0]]);
return result;
}
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const k = 3;
console.log(maxSubarrays(array, k));
Output
[ 3, 4, 5, 6, 7, 8, 9, 10 ]
Time Complexity: O(n)
Auxiliary Space: 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