Optimal Approach
The optimal approach utilizes a deque (double-ended queue) to efficiently find the maximum element in each window as it slides from left to right. Define a function “maxSlidingWindowOptimal” with parameters “nums” and “k”. Initialize an empty “result” array to store maximum elements. Use a deque to maintain indices of elements in decreasing order. Iterate through “nums”, updating the deque according to the algorithm. Store max element based on deque’s first element, push to “result”.
Example: The example below shows Sliding Window Maximum using JavaScript using the Optimal Approach.
function maxSlideWinOpt(nums, k) {
const result = [];
const deque = [];
for (let i = 0; i < nums.length; i++) {
while (deque.length && nums[i] >= nums[deque[deque.length - 1]]) {
deque.pop();
}
deque.push(i);
if (i - deque[0] + 1 > k) {
deque.shift();
}
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlideWinOpt(nums, k));
Output
[ 3, 3, 5, 5, 6, 7 ]
Time Complexity: O(n), where n is the length of the input array nums.
Space Complexity: O(k), where k is the size of the sliding window.
Sliding Window Maximum using JavaScript
Given an array of integers and a window size, the task is to find the maximum element in each window of the array as it slides from left to right.
Below are the approaches to solve the Sliding Window Maximum problem using JavaScript:
Table of Content
- Brute Force Approach
- Optimal Approach