239. Sliding Window Maximum | LeetCode Solution

 239. Sliding Window Maximum | LeetCode

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.

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 <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

Solution:

The first thing which comes to our mind is that we can go to every index and then start another loop to go to the next k element and store the maximum.

This will definitely exceed the Time Limit:

class Solution {

public:

    vector<int> maxSlidingWindow(vector<int>& v, int k) {

        vector<int>ans;

        for(int i=0; i<=v.size()-k; i++){

            int temp=INT_MIN;

            for(int j=i; j<i+k && j<v.size(); j++)temp=max(temp,v[j]);

            ans.push_back(temp);

        }

        return ans;

    }

};

So how can we optimize this solution?  Heard of Deque we can use that here. In deque, we can insert and pop from both back and front. We will keep a deque and the maximum elements in that. At first, we will check whether the maximum element ( from front) belong to the current window or not if not we will pop until we get the maximum element in the current window of size k.

Now we will check from the back if the current element is greater than the element in the back of deque if yes we will pop until we find a greater element in the back of deque. We will then insert the current element in the back of deque and the front of deque will be the maximum element in the window of size k.

sdf