Sliding Window - Sliding Window Maximum

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.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window positionMax
----------------------
[1 3 -1] -3 5 3 6 73
1 [3 -1 -3] 5 3 6 73
1 3 [-1 -3 5] 3 6 75
1 3 -1 [-3 5 3] 6 75
1 3 -1 -3 [5 3 6] 76
1 3 -1 -3 5 [3 6 7]7

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

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

Solution 1 - Using sliding window technique, and a Deque keep track of maximum numbers with the sliding window of k length

In this approach, we will use a Deque data structure (double ended queue) to store elements such a way that, it contains elements in decreasing order. So, whenever we reach a sliding window of length k, we can simply poll the head element and add that result.

So, how do we achieve this ?

We will start iterating through the input array nums, and store the element at head position in the Deque.

If the next element is larger than the head element, then remove the head element and add current element as new head.
If the the next element is less than head element, then add it to the tail.

By doing so, we are keeping lergest element at the head. When we reach a sliding window of length k, take the element at head position from Deque and add it to the result, also move sliding window to next position, when we move left position of sliding window, check if the head position is that left pointer element, if it is, then remove it from the Deque.

Let's understand this with an example, nums = [1,3,-1,-3,5,3,6,7] and

Let's start with the first element in nums array, 1 add it to theDeque 1, , , , , , , .
Next element in nums array is 3, compare it with head of deque, it is greater than the head element 1, so remove the head and add current element as head, so the deque becomes 3, , , , , , , .
Next element in nums array is -1, compare it with head of deque, it is less than the head element 1, so add it to the tail, so the deque becomes 3,-1, , , , , , , .
Now, we have reached sliding window size of k, so take the head element and add it to the result 3, also move left pointer element, check if that element is the head, left pointer (index =0) element is 1 and this is not same as head, so continue to next element.
Next element is -3, since it is less than the head element 3, so add it to the deque, it becomes 3,-1,-3, , , , , , , .
Now, we have reached sliding window size of k, so take the head element and add it to the result 3, also move left pointer element, check if that element is the head, left pointer (index =1) element is 3 and this is same as head, so remove it from deque and continue to next element, so the deque becomes -1,-3, , , , , , , .
Next element is 5, since it is greater than the head element -1, remove the head, and next element -3 is also less than current element, so remove this element as well. So the deque becomes 5, , , , , , , .
Now, we have reached sliding window size of k, so take the head element and add it to the result 5, also move left pointer element, check if that element is the head, left pointer (index =2) element is -1 and this is not same as head, so continue to next element.
Next element is 3, since it is less than the head element 5, so add it to the tail, so the deque becomes 5,3, , , , , , , .
Now, we have reached sliding window size of k, so take the head element and add it to the result 5, also move left pointer element, check if that element is the head, left pointer (index =3) element is -3 and this is not same as head, so continue to next element.
Next element is 6, since it is greater than the head element 5, remove the head, and next element 3 is also less than current element, so remove this element as well. So the deque becomes 6, , , , , , , .
Now, we have reached sliding window size of k, so take the head element and add it to the result 6, also move left pointer element, check if that element is the head, left pointer (index =4) element is 5 and this is not same as head, so continue to next element.
Next element is 7, since it is greater than the head element 6, remove the head. So the deque becomes 7, , , , , , , .
Now, we have reached sliding window size of k, so take the head element and add it to the result 7 and we have reached the end of array.

import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; public class SlidingWindowMaximum { static int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> q = new ArrayDeque<>(nums.length); int left =0; int right =0; int[] ans = new int[nums.length - k+1]; int ai =0; while (right <nums.length) { while(!q.isEmpty() && q.peekLast() < nums[right]){ q.pollLast(); } q.offerLast(nums[right]); if(k<=right-left+1) { ans[ai++] = q.peekFirst(); if(q.peekFirst() == nums[left++]) { q.pollFirst(); } } right++; } return ans; } public static void main(String[] args) { System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3))); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input array nums.
Space complexity: O(n), since we are storing input array elements into a Deque.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: