Sliding Window Maximum

Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

Problem Statement

Given an array aa, and an integer kk, find the maximum element for every contiguous subarray of size kk.

Examples

Example 1

Input :

Output :

Explanation :

  • Maximum of first window i.e.[5,1,0]i.e. [5, -1, 0] is 5.
  • Maximum of second window i.e.[1,0,9]i.e. [-1, 0, 9] is 9.
  • Maximum of third window i.e.[0,9,4]i.e. [0, 9, -4] is 9.
  • Maximum of fourth window i.e.[9,4,7]i.e. [9, -4, 7] is 9.
  • Maximum of fifth window i.e.[4,7,1]i.e. [-4, 7, 1] is 7.

sliding window maximum example

Example 2

Input :

Output :

Explanation :

  • Maximum of first window i.e.[2,3,6,6,1]i.e. [2, -3, 6, 6, -1] is 6.
  • Maximum of second window i.e.[3,6,6,1,7]i.e. [-3, 6, 6, -1, 7] is 7.
  • Maximum of third window i.e.[6,6,1,7,1]i.e. [6, 6, -1, 7, 1] is 7.
  • Maximum of fourth window i.e.[6,1,7,1,8]i.e. [6, -1, 7, 1, 8] is 7.

Constraints

  • 0a.length1050\leq a.length \leq 10^5
  • 109a[i]109-10^9 \leq a[i] \leq 10^9
  • 1kn1\leq k\leq n

Approach 1: Brute Force

The first approach that comes to our mind while reading the problem, is to run two nested loops to find the maximum element of each window of size kk.

The idea is quite basic, we will use two nested for loops, where the first loop will mark the starting point (say ii) of the subarray of length kk, and the inner loop will run from ii to i+ki+k and find the maximum element in the range.

The algorithm is as follows -

  • Let's say we have an array aa of size nn, we need to print the maximum of every window of size kk.
  • Iterate from i=0i=0 to i=nki=n-k and do the following -
    • Declare a variable (say maxmax) and initialize it very small value (say -\infty).
    • Iterate from j=ij=i to j=i+k1j=i+k-1 and do the following -
      • If a[j]>maxa[j]>max, update the value of maxmax to a[j]a[j].
    • Print minmin, which now denotes the maximum element of the window of size kk starting from ii.

Note that in the outer loop we are iterating till i=nki=n-k because the starting point of the last window will be nkn-k.

Pseudocode

Java Implementation

C++ Implementation

Python Implementation

Output

Complexity Analysis

  • Time Complexity - The outer loops run for nk+1n-k+1 times while the inner loops run for kk times in each iteration. Hence the overall time complexity is O((nk+1)×k)O((n-k+1)\times k) which is equivalent to O(n×k)O(n\times k).
  • Space Complexity - Since we are not using any extra space. The overall space complexity is O(1)O(1).

Approach 2: Using Self-Balancing BST

In the last section, we used a loop to iterate for each window and find its maximum element which had cost us O(n×k)O(n\times k) time on an average. Using Self-Balancing BST (AVL Tree) we can reduce this to O(nlogk)O(n\log k).

As we have seen in AVL Tress, all the operations like searching, deleting, and inserting a node are O(logn)O(\log{n}) time taking operations in both the average case and the worst case. If you are interested in knowing, why it is so, please go through the detailed article on AVL Trees.

The main idea is to, insert the first kk elements in the AVL tree and then for each i=ki=k to i=n1i=n-1 find the largest element present in the tree (which denotes the maximum element of the current window), remove elements that are no longer part of the window, and insert the element which is added to the window during ithi^{th} iteration. Since at most kk nodes can be present in the tree at any instant of time, therefore all these operations will cost O(k)O(k) time on an average. And we are iterating for nn times, which makes the overall time complexity O(nlogk)O(n\log{k}) which is pretty efficient.

The algorithm is as follows -

  • Define an AVL tree (say tree).
  • Iterate through the first kk elements of the array, and insert them in the tree.
  • Iterate from i=ki=k to i=n1i=n-1 and do the following -
    • Print the maximum element of the tree.
    • Delete the element at index (ik)(i-k) from the tree, as it is no longer part of the window.
    • Insert the ithi^{th} element of the array in the AVL tree.
  • Print the maximum element of the tree, this denotes the maximum element of the last window of size k.

Pseudocode

Note that the Code of AVL tree is very large and complicated, hence it's not worth it to discuss it here therefore we are just importing the code already written to implement it. If you are interested to learn more about AVL trees, kindly go through this.

Java Implementation

C++ Implementation

Complexity Analysis

  • Time Complexity - For each ii ranging from 0 to n1n-1, we are doing at most O(logn)O(\log{n}) operations i.e.i.e. removing from AVL tree and inserting in it. Hence the time complexity is O(nlogn)O(n\log{n}).
  • Space Complexity - The maximum number of nodes present in the AVL tree can reach up to kk at any instant of time. Hence the space complexity is O(k)O(k).

Approach 3: Max-Heap

In the previous approach, we have seen how we can find the sliding window maximum efficiently using AVL trees. This approach is also very similar to the previous one, here we will be using the Max-Heaps instead of AVL trees, and the rest of the logic will be the same only.

The idea is to insert all the elements which are part of the first window of size kk, then find the maximum among them and print it. Now before moving to the next window, remove the element that is no longer the part of any subsequent window, and add the element that will the part of the further window(s).

The algorithm is as follows -

  • Define a Heap (PriorityQueue), let it be pq. Make sure that it is a max-heap and not a min-heap.
  • Iterate through the first kk elements of the array, and insert them into the heap.
  • Iterate from i=ki=k to i=n1i=n-1 and do the following -
    • Print the maximum element of the heap i.e.i.e. root node.
    • Remove the element at index (ik)(i-k) from the heap, as it is no longer part of the window.
    • Insert ithi^{th} element of the array in the Max-Heap.
  • Print the maximum element of pq, this denotes the maximum element of the last window of size k.

Pseudocode

Java Implementation

C++ Implementation

Output

Complexity Analysis

  • Time Complexity - For each element we are performing logarithmic time operations (Inserting, removing from the heap). Due to this, the time complexity is O(nlogk)O(n\log{k}).
  • Space Complexity - The size of the heap can reach up to kk, therefore the space complexity is O(k)O(k).

Approach 4: Deque

An important observation that we can easily make here is that, we can only consider the promising candidates of the current window. An element is considered to be promising for being a sliding window maximum if it lies in the current window and it is greatest among all the elements that lies in the window range (towards the right side).

To implement this functionality, we will introduce an interesting data structure i.e.i.e. monotonic doubly-ended queue. Don't get afraid of the name, it is just a doubly ended queue in which elements from head to tail is in decreasing order (hence it is named monotonic).

To transform a simple doubly-ended queue into a monotonic doubly ended queue, we will modify the push operation so that - "Before we push x in the queue, we pop out all elements less than x".

The algorithm is as follows -

  • Create a doubly ended queue (say dqdq) of size kk.
  • Iterate from i=0i=0 to i=k1i=k-1 and do the following -
    • Pop out all elements from tail of dqdq until the inequality dq.taila[i]dq.tail\leq a[i] holds true.
    • Push a[i]a[i] in dqdq.
  • Now iterate from i=ki=k to i=ni=n and do the following -
    • Print the element at the head of dqdq, this denotes the maximum element of the current window.
    • Pop all the elements from the head of dqdq which no longer lie in the current window.
    • Pop all the elements from the tail of dqdq which are smaller than or equal to a[i]a[i].
    • Push a[i]a[i] into the queue.
  • Print the element at the head of the queue, this marks the maximum element of the last window.

Psuedocode

Java Implementation

C++ Implementation

Python Implementation

Output

Complexity Analysis

  • Time Complexity - It can be noticed that every element of the array is pushed and popper at most once. Hence there are at max 2×n2\times n operations, and hence the time complexity is O(n)O(n).
  • Space Complexity - Since the maximum size of the queue can reach up to kk, the space complexity is O(k)O(k). Also, the max value kk can attain is nn, hence we can say the upper bound is O(n)O(n) in the worst case.

Approach 5: Using Dynamic Programming

In all the approaches we have seen in the previous sections, we were processing the elements as we are sliding our window (towards the right). But if we can store some sort of information that can be used in the future to find the maximum element of the window, that will be more than good.

One good idea is - for each 0 <= i < n, store the index of next greater element to the right. Now let's see how this can help us to find the maximum element of each window of size kk.

We will iterate from i=0i=0 to i=nk1i=n-k-1, and for each window starting at the ithi^{th} index, we will find the greatest element that lies in the current window, and in case there is no greater element than the ithi^{th} element in the range of window we will consider it to be the greatest element of the window.

The algorithm is as follows - We will split this program into two parts, In part 1 for each element, we will find the index of the next greater element toward the right, and in part 2 we will find the sliding window maximum.

Part 1 -

  • Define an array (say right) of size nn, where right[i] will store index of the next greater element towards the right.
  • Assign nn to right[n-1], because for the last element we consider there is an imaginary number at the nthn^{th} position which is very large.
  • Iterate from i=n2i=n-2 to i=0i=0 and do the following -
    • Assume the element at index i+1i+1 is the next greater element, so store i+1i+1 in a variable (say p).
    • Now till p<np<n (p lies in array bounds) and a[p]a[i]a[p] \leq a[i] (element at index p is smaller than or equal to element at index i), update the value of p to right[p] (Index of next greater element for a[p]).
    • Store the final value of p in right[i].

Part 2 -

  • Initialize two variables (say i and j), where i will be used to iterate over the array and j will be used to mark the maximum element of the window.
  • Iterate from i=0i=0 to i=nk1i = n - k - 1 and do the following -
    • If j is less than i i.e.i.e. the current maximum element is no longer in the window then assign the value of i to j.
    • Iterate till right[j] lies in the current window and update value of j as j = right[j].
    • If now the value of j is n, it means a[i] is the greatest element of the current window, hence print it.
    • Otherwise, print a[j] that denotes the greatest element that lies in the window.

Pseudocode

Java Implementation

C++ Implementation

Python Implementation

Output

Complexity Analysis

  • Time Complexity - Both part 1 and part 2 of the algorithm requires O(n)O(n) time to get executed, hence the overall time complexity is O(n+n)O(n)O(n+n) \simeq O(n).
  • Space Complexity - Since we have used the right array to store indices of the next greater element which is of size nn. The overall space complexity is O(n)O(n).

Conclusion

  • Sliding Window Maximum is nothing but the maximum element present in each contiguous subarray of size kk (given).
  • They can be found in O(n2)O(n^2) time when using the naive brute-force approach.
  • However, with certain optimizations it can be brought down to O(nlogk)O(n\log{k}) by using Heaps or AVL Trees.
  • Optimally it can be solved in linear time complexity either using dynamic programming or Monotonic Deque.