Skip to main content

Sliding Window Maximum

Problem Description​

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Examples​

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints​

  • 1 <= nums.length <= 10^5
  • 10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

Solution for Sliding Window Maximum Problem​

Approach​

Sliding Window Approach:​
  • The sliding window technique involves maintaining a window of fixed size (k) as it slides from the beginning to the end of the array. This allows us to efficiently compute the desired result for each window without redundant computations.
HashMap Usage:​
  • A hashmap (or hash table) is utilized to keep track of elements within the current window and their frequencies (or counts). The hashmap helps in quickly determining the maximum element within the current window without having to scan the entire window repeatedly.
Initialization:​

-Initialize two pointers, left and right, to define the current window. Initially, set both pointers to the beginning of the array.

Building the Initial Window:​
  • Extend the right pointer to expand the window until its size reaches k. During this expansion: Update the hashmap to include the frequency of each element in the current window.
Maintaining the Hashmap:​
  • As you slide the window (right pointer moves one step to the right), update the hashmap:
  • Increment the count of the element pointed by right.
  • Adjust the hashmap to ensure it reflects the elements and their counts within the current window.
Finding the Maximum:​
  • Once the window size equals k, retrieve the maximum value from the hashmap. Depending on the requirement (maximum or minimum), this can be determined efficiently:
  • For maximum: Iterate through the hashmap (or use additional data structures like max heap) to find the maximum element.
  • For minimum: Similarly, find the minimum element within the hashmap.
Adjusting the Window:​
  • Slide the window to the right (left pointer moves one step to the right):
  • Decrement the count of the element pointed by left.
  • Remove elements from the hashmap if their count drops to zero to maintain accuracy in the calculation.
Output the Result:​

  • Store or directly process the result for each window (e.g., store the maximum value found for each window).

  • Repeat Until Completion:

  • Continue this process until the right pointer has traversed the entire array.

Implementation​

Live Editor
function Solution(arr) {
var maxSlidingWindow = function(nums, k) {
let maxQueue = [];
let result = [];

for (let i = 0; i < nums.length; i++) {
    // Remove elements from maxQueue that are out of the current window
    while (maxQueue.length > 0 && maxQueue[maxQueue.length - 1] < nums[i]) {
        maxQueue.pop();
    }
    
    // Add current element to maxQueue
    maxQueue.push(nums[i]);
    
    // Remove elements from maxQueue that are out of the current window range
    if (i >= k - 1) {
        result.push(maxQueue[0]);
        if (nums[i - k + 1] === maxQueue[0]) {
            maxQueue.shift();
        }
    }
}

return result;
};

  const input = [1,3,-1,-3,5,3,6,7]
  const  k = 3
  const output =maxSlidingWindow(input , k)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(n)O(n) because of traversing
  • Space Complexity: O(n)O(n) because of hashmap

Code in Different Languages​

Written by @hiteshgahanolia
var maxSlidingWindow = function(nums, k) {
 let maxQueue = [];
 let result = [];
 
 for (let i = 0; i < nums.length; i++) {
     // Remove elements from maxQueue that are out of the current window
     while (maxQueue.length > 0 && maxQueue[maxQueue.length - 1] < nums[i]) {
         maxQueue.pop();
     }
     
     // Add current element to maxQueue
     maxQueue.push(nums[i]);
     
     // Remove elements from maxQueue that are out of the current window range
     if (i >= k - 1) {
         result.push(maxQueue[0]);
         if (nums[i - k + 1] === maxQueue[0]) {
             maxQueue.shift();
         }
     }
 }
 
 return result;
};

References​