Sliding Window Maximum

Problem Statement: Sliding Window Maximum

sliding window maximum : Given an array and an integer K in sliding window maximum problem, find the maximum for each and every contiguous subarray of size k.

Examples:

arr[] = [1, 2, 3, 1, 4, 5, 2, 3, 6]

K = 3

Output: 3 3 4 5 5 5 6

Explanation

Maximum of 1, 2, 3 is 3

Maximum of 2, 3, 1 is 3

Maximum of 3, 1, 4 is 4

Maximum of 1, 4, 5 is 5

Maximum of 4, 5, 2 is 5

Maximum of 5, 2, 3 is 5

Maximum of 2, 3, 6 is 6

Approach 1: Brute Force

The very first approach that comes to our mind is to run a nested loop, the outer loop which will mark the starting point of the subarray of length k, the inner loop will run from the starting index to index+k, k elements from starting index and print the maximum element among these k elements. Time complexity will be O(n * k) which is not the optimal one so we need to optimise it

Crack your next tech interview with confidence!

Approach 2: Using Deque

We can use a double-ended queue to keep only the indices of those elements which are useful. The use of deque is to add and drop elements from both the ends of a queue. We will slide the window of K elements by “dropping” the first element and “adding” the next element after the window to move it forward.

The deque will keep the index of the maximum element at the front and also at a time, it will delete all the unnecessary elements from the window. You can look at the solution steps for more explanation

Algorithm:

1. Create a deque and an ans list to strore the final ans

2. loop the the given input list

3. pop the deque from the right untill the rightmost element of the queue is greater than the current element in the loop (note that the deque is only storing the index)

4. Insert the current elements index to the right of the deque. If the the leftmost element of the deque is equal to i-k then it is no loger under consideration so we pop it

5. For every cycle of the loop after the threshold i >=k-1 we push it to the ans list

#include<bits/stdc++.h>

using namespace std;

vector < int > maxSlidingWindow(vector < int > & nums, int k) {
  deque < int > dq;
  vector < int > ans;
  for (int i = 0; i < nums.size(); i++) {
    if (!dq.empty() && dq.front() == i - k) dq.pop_front();

    while (!dq.empty() && nums[dq.back()] < nums[i])
      dq.pop_back();

    dq.push_back(i);
    if (i >= k - 1) ans.push_back(nums[dq.front()]);
  }
  return ans;
}
int main() {
  int i, j, n, k = 3, x;
  vector < int > arr {4,0,-1,3,5,3,6,8};
  vector < int > ans;
  ans = maxSlidingWindow(arr, k);
  cout << "Maximum element in every " << k << " window " << endl;
  for (i = 0; i < ans.size(); i++)
    cout << ans[i] << " ";
  return 0;
}

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums, k):
        result = []
        dq = deque()
        for i in range(len(nums)):
            # make sure the first elment in the queue is the largest one
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()
            dq.append(i)
            # if the largest one is not in the current 
#sliding window we should pop it
            while dq and i - dq[0] >= k:
                dq.popleft()
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result
ob1 = Solution()
print(ob1.maxSlidingWindow([1, 2, 3, 1, 4, 5, 2, 3, 6], 3))

Time Complexity: O(2 * n) (Every element is added and removed at most once)

Auxiliary Space: O(K)