Leetcode 239. Sliding Window Maximum

Problem Explanation

The problem asks us to implement a sliding window of a given size "k" which traverses through an array from left to right. The challenge comes in finding the maximum value in each window frame. To illustrate, let's look at the following example using an array [1,3,-1,-3,5,3,6,7] with a window size k = 3.

The window moves through the array like this:

1
2
3Window position                Max
4---------------               -----
5[1  3  -1] -3  5  3  6  7       3
6 1 [3  -1  -3] 5  3  6  7       3
7 1  3 [-1  -3  5] 3  6  7       5
8 1  3  -1 [-3  5  3] 6  7       5
9 1  3  -1  -3 [5  3  6] 7       6
10 1  3  -1  -3  5 [3  6  7]      7

The maximum values in each window are saved and output in an array [3,3,5,5,6,7].

Approach Explanation

The simplest way to solve the problem would be to iterate over each window and find the maximum. However, this approach will take O(n*k) time which might not be optimal for large inputs.

A better approach is to take advantage of a data structure such as a deque (double-ended queue) which can insert and delete elements at both ends in O(1) time. While traversing the array, we keep track of the maximum element in the current window in the deque.

As we move forward, if the current element is greater than the back of the deque, we remove elements from the back. When we move out of window, we check if the front element of deque is still in window, if it's not in window then we remove it. The maximum element of the window will always be at the front of the deque.

Python Solution

1
2python
3from collections import deque
4
5class Solution:
6    def maxSlidingWindow(self, nums, k):
7        deq, n, ans = deque([0]), len(nums), []
8
9        for i in range (n):
10            while deq and deq[0] < i - k + 1:
11                deq.popleft()
12            
13            while deq and nums[i] > nums[deq[-1]]:
14                deq.pop()
15            
16            deq.append(i)
17            
18            ans.append(nums[deq[0]])
19        
20        return ans[k-1:]

Java Solution

1
2java
3class Solution {
4    public int[] maxSlidingWindow(int[] nums, int k) {
5        if(nums.length == 0) return new int[0];
6        
7        Deque<Integer> deque = new ArrayDeque<>();
8        int[] result = new int[nums.length-k+1];
9        for(int i=0; i<nums.length; i++) {
10            // remove numbers out of range k
11            while(!deque.isEmpty() && deque.peek()<i-k+1) deque.poll();
12            
13            // remove smaller numbers within range k as they are useless
14            while(!deque.isEmpty() && nums[deque.peekLast()]<nums[i]) deque.pollLast();
15            
16            deque.offer(i);
17            if(i-k+1>=0) result[i-k+1] = nums[deque.peek()];
18        }
19    
20        return result;
21    }
22}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
6        vector<int> res;
7        deque<int> q;
8        for (int i = 0; i < nums.size(); ++i) {
9            if (!q.empty() && q.front() == i - k) q.pop_front();
10            while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
11            q.push_back(i);
12            if (i >= k - 1) res.push_back(nums[q.front()]);
13        }
14        return res;
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public int[] MaxSlidingWindow(int[] nums, int k) {
5        if (!nums.Any()) return new int[0];
6        
7        var deque = new LinkedList<int>();
8        var result = new int[nums.Length - k + 1];
9        
10        for (int i = 0; i<nums.Length; i++) 
11        {
12            if (deque.Any() && deque.First.Value < i-k+1) 
13                deque.RemoveFirst();
14            
15            while (deque.Any()&& nums[deque.Last.Value] < nums[i]) 
16                deque.RemoveLast();
17                
18            deque.AddLast(i);
19            if (i-k+1 >= 0) 
20                result[i-k+1] = nums[deque.First.Value];
21        }
22        return result;
23    }
24}

JavaScript Solution

1
2javascript
3var maxSlidingWindow = function(nums, k) {
4    let deque = [];  // stores index
5    let res = [];
6    
7    for(let i=0; i<nums.length; i++) {
8
9        while(deque && nums[deque[deque.length-1]]<nums[i]) {
10            deque.pop();
11        }
12
13        deque.push(i);
14        
15        // When (i+1)-deque[0]===k , means deque[0] is out of window, so we shift it from left
16        if(i+1-deque[0]===k) deque.shift();
17        // if window has k elements add to results(print only when we the window is full)
18        (i+1>=k) && res.push(nums[deque[0]]);
19    }
20    return res;
21};

That's it! We've now successfully tackled the problem and all the language solutions.The C++ solution uses a similar approach of deque to solve the problem. It removes the numbers out of range and smaller numbers within the sliding window, and then it pushes back the current index to the deque. When the current index reaches k-1 it starts to push back the maximum of each window into the result vector.

For the C# solution, it is quite similar to the Java solution. The difference is that C# uses a doubly-linked list named LinkedList to store the indices which can effectively operate on both ends of the list.

The JavaScript solution is also quite similar as it pushes the indexes of the currently largest elements within the window into the deque. This way, it can easily discard the maximum elements that are no longer within the window when sliding the window to the right.

This problem reminds us of the powerful usage of the Double-ended Queue (deque). By utilizing this data structure, we can optimize the time complexity to O(n) which is beneficial for processing large datasets. By pushing back and popping out the elements at both ends, we can keep track of the maximum element within the window effectively.

In summary, the sliding window problem can be a challenging one, especially when asked to find the maximum for each window. By leveraging the deque, we can greatly enhance the computational efficiency and solve the problem in an elegant manner. This problem not only enhances our problem-solving skills but also deepens our understanding of the deque data structure. And these skills can be extremely useful for dealing with similar problems in the future.