Maximum of all Subarrays of size K (Sliding Window Maximum)

We have been given an integer array of size ‘n’ and an integer ‘k’, we need to print/store the maximum of all the subarrays of size k.

Example -

Input - a[] ={5, 12, 3, 8, 20, 35}, k=3
Output - 12 12 20 35 

Explanation -

1. All subarrays of size k are - {5, 12, 3}, {12, 3, 8}, {3, 8, 20}, {8, 20, 35}.
2. The maximums of these subarrays are 12, 12, 20, and 35, respectively.

Simple Approach (Brute Force) -

The idea used in this approach is very simple, we will use two nested loops to mark the starting and ending point of the window/subarray. Let’s look at the algorithm to have a better understanding of this.

Algorithm:

1. The outer loop will run from 0 to “n-k”, it will mark the starting point of the subarray.
2. The inner loop will run k time from the current index of the outer loop, which at the end marks the last index of the subarray.
3. In the inner loop, while iterating through the subarray of size ‘k’, we can find the maximum element present inside it.
4. Then, at last, we will print it.

Below is the implementation of the above approach -

CPP:

#include <bits/stdc++.h>
using namespace std;
void printMaxOfEverySbarrayOfSizeK(int a[],int n,int k){
    
    // Start the loop form 
    // 0 to n-k to mark
    // starting point of
    // the subarray.
    for(int i=0;i<=n-k;i++)
    {
        
        int maximum=a[i];
        // Check for maximum in
        // k sized subarray.
        for(int j=1;j<k;j++)
        {
            maximum=max(maximum,a[i+j]);
        }
        
        // Print the maximum found. 
        cout<<maximum<<" ";
    }
    cout<<endl;
}
int main() {
    int arr[]={5, 12, 3, 8, 20, 35};
    int n=sizeof(arr)/sizeof(arr[0]);
    int k=3;
    
    printMaxOfEverySbarrayOfSizeK(arr,n,k);
    	
}

Output:

12 12 20 35 

JAVA:

import java.util.*;
public class Main {
    public static void printMaxOfEverySbarrayOfSizeK(int a[],int n,int k){
        
        // Start the loop form 
        // 0 to n-k to mark
        // starting point of
        // the subarray.
        for(int i=0;i<=n-k;i++)
        {
            
            int maximum=a[i];
            // Check for maximum in
            // k sized subarray.
            for(int j=1;j<k;j++)
            {
                maximum=Math.max(maximum,a[i+j]);
            }
            
            // Print the maximum found. 
            System.out.print(maximum+" ");
        }
        System.out.println();
    }
	public static void main (String[] args) {
	    
	    int arr[]={5, 12, 3, 8, 20, 35};
	    int n=arr.length;
	    int k=3;
	    
	    printMaxOfEverySbarrayOfSizeK(arr,n,k);
	}
}

Output:

12 12 20 35 

Python:

def printMaxOfEverySbarrayOfSizeK(a, n, k):
    # Start the loop form
    # 0 to n-k to mark
    # starting point of
    # the subarray.
    for i in range(n - k + 1):
        max = arr[i]
        # Check for maximum in
        # k sized subarray.
        for j in range(1, k):
            if arr[i + j] > max:
                max = arr[i + j]
        # Print the maximum found.
        print(str(max) + " ", end = "")

# Driver method
if __name__=="__main__":
    arr = [5, 12, 3, 8, 20, 35]
    n = len(arr)
    k = 3
    printMaxOfEverySbarrayOfSizeK(arr,n,k)

Output:

12 12 20 35 

Complexity Analysis:

• Time Complexity : O(n*k)
• Space Complexity : O(1), Since no extra space is required.

Efficient Approach

In this approach, we will use a Double-ended queue, i.e., Deque, to store only those elements which can be a possible answer. An element is a possible answer if and only if it belongs to the current window and it is greater than every other element on the right side. We will implement it in such a way that the element at the front of the Deque is the largest, and the element at the rear end is the smallest. Let’s have a look at the algorithm for a better understanding -

Algorithm:

1. Create a Double-ended queue.
2. Run a for loop from 0 to k-1 and insert all the elements also, during every iteration, check if the element at the rear end of Deque is smaller than the current element if yes, then remove it till every element on the left side is greater than the current element.
3. Now run a loop to insert the rest of the element, i.e., form k to n-1.
4. Print the element which is in front of the Deque.
5. During each iteration, remove the element which is out of the current window also do a check exactly like step 2 before inserting the current element at the rear end.
6. At last, the front element of Deque is the Maximum element of the last window, so we also have to print it.

Below is the implementation of the above approach -

CPP:

#include <bits/stdc++.h>
using namespace std;
void printMaxOfEverySbarrayOfSizeK(int a[],int n,int k){
    deque <int> dq(k);
        
    // Insert the first k elements 
    for(int i=0;i<k;i++) { 
        // removeLast if current element 
        // is smaller than lastElement. 
        while(!dq.empty()&&a[i]>=a[dq.back()])
        dq.pop_back();
        
        // Add i at rear
        // end of Deque.
        dq.push_back(i);
    }
    
    // Iterate through the rest of the array.
    for(int i=k;i<n;i++)
    {
        // Print the current
        // greatest element. 
        cout<<a[dq.front()]<<" ";
        
        // remove the elements 
        // which is out of the window. 
        while(!dq.empty()&&dq.back()<=i-k) 
         dq.pop_front(); 
        // removeLast if current element 
        // is smaller than lastElement. 
        while(!dq.empty()&&a[i]>=a[dq.back()])
        dq.pop_back();
        dq.push_back(i);
    }
    // Print greatest 
    // element of the last window.
    cout<<a[dq.front()]<<" ";
}

int main() {
	int arr[]={5, 12, 3, 8, 20, 35};
    int n=sizeof(arr)/sizeof(arr[0]);
    int k=3;
    
    printMaxOfEverySbarrayOfSizeK(arr,n,k);
	    
    cout<<endl;
	return 0;
}

Output:

12 12 20 35 

Java:

import java.util.*;
public class Main {
    public static void printMaxOfEverySbarrayOfSizeK(int a[],int n,int k){
        // Create the Deque
        Deque <integer> dq = new LinkedList();
        
        // Insert the first k elements 
        for(int i=0;i<k;i++) 
        { 
            // removeLast if current element 
            // is smaller than lastElement. 
            while(!dq.isEmpty()&&a[i]>=a[dq.peekLast()])
            dq.removeLast();
            
            // Add i at rear
            // end of Deque.
            dq.addLast(i);
        }
        
        // Iterate through the rest of the array.
        for(int i=k;i<n;i++)
        {
            // Print the current
            // greatest element. 
            System.out.print(a[dq.peek()]+" ");
            
            // remove the elements 
            // which is out of the window. 
            while(!dq.isEmpty()&&dq.peek()<=i-k) 
                 dq.removeFirst(); 
           // removeLast if current element 
           // is smaller than lastElement. 
           while(!dq.isEmpty()&&a[i]>=a[dq.peekLast()])
            dq.removeLast();
            dq.addLast(i);
        }
        // Print greatest 
        // element of the last window.
        System.out.print(a[dq.peek()]+" ");
    }
    
	public static void main (String[] args){
	    
	    int arr[]={5, 12, 3, 8, 20, 35};
	    int n=arr.length;
	    int k=3;
	    
	    printMaxOfEverySbarrayOfSizeK(arr,n,k);
	    
        System.out.println();
	}
}

Output:

12 12 20 35 

Python:

from collections import deque
  
def printMaxOfEverySbarrayOfSizeK(arr, n, k):
      
    # Create the Deque
    dq = deque()
      
    # Insert the first k elements 
    for i in range(k):
        # removeLast if current element
        # is smaller than lastElement.
        while dq and arr[i] >= arr[dq[-1]] :
            dq.pop()
          
        # Add i at rear
        # end of Deque.
        dq.append(i);
          
    # Iterate through the rest of the array.
    for i in range(k, n):
          
        # Print the current
        # greatest element. 
        print(str(arr[dq[0]]) + " ", end = "")
          
        # remove the elements 
        # which is out of the window. 
        while dq and dq[0] <= i-k: 
            dq.popleft() 
        # removeLast if current element 
        # is smaller than lastElement. 
        while dq and arr[i] >= arr[dq[-1]] :
            dq.pop()
          
        # Add current element at the rear of dq
        dq.append(i)
      
    # Print greatest 
    # element of last window.
    print(str(arr[dq[0]]))
      
# Driver code
if __name__=="__main__":
    arr = [5, 12, 3, 8, 20, 35]
    k = 3
    printMaxOfEverySbarrayOfSizeK(arr, len(arr), k)

Output:

12 12 20 35 

Complexity Analysis:

• Time Complexity : O(n), Since Only 2n operations (in the worst case), are done.
• Auxiliary Space : O(k), Because we used Deque to store k elements.

Another Efficient Approach

This approach is quite similar to the above one, but in this one, we will use Stacks instead of Queue. Time and Space complexities are also the same as the Deque-based approach.  Here we will use the concept of the next greater element approach. For each element, we will find the interval in which it is the greatest element.  Have a look at the algorithm for a better understanding -

Algorithm:

1. Create an array “upto”, which will store the index until which current element is greatest.
2. Create a stack and push 0 to it; it will be used to determine values to be used up upto.
3. Run a loop from 1 to n-1.
4. Pop-out all the indexes from the stack for which a[st.top] is less than the current element, and we will update the value of upto[stack.top] to current index-1.
5. Then push the current index ‘i’ to the stack.
6. While stack is not empty make upto[s.top] = n-1
7. Run a loop from 0 to n-k, and inside each loop, check upto which position the current element is max as well as inside the window.

Below is the implementation of the above approach -

CPP:

#include <bits/stdc++.h>
using namespace std;
void printMaxOfEverySbarrayOfSizeK(int a[],int n,int k){
    // Create the upto array.
        int upto[n];
  
        // Create the stack.
        stack <int> st;
        st.push(0);
        
        // Run loop form 1 to n-1 
        for (int i = 1; i < n; i++)
        {
            //Pop out all the indexes from the 
            //stack for which a[st.top] is less than
            //current element and we will update the 
            //value of upto[stack.top] to current index-1.
            while (!st.empty() && a[st.top()] < a[i])
            {
                upto[st.top()] = i - 1;
                st.pop();
            }
            //Push i
            st.push(i);
        }
        // While stack is not 
        //empty make upto[s.top] = n-1.
        while (!st.empty())
        {
            upto[st.top()] = n - 1;
            st.pop();
        }
        int j = 0;
        for (int i = 0; i <= n - k; i++)
        {
  
            // j < i is to check whether the
            // jth element is outside the window
            while (j < i || upto[j] < i + k - 1)
            {
                j++;
            }
            cout<<a[j]<<" ";
        }
}

int main() {
	int arr[]={5, 12, 3, 8, 20, 35};
    int n=sizeof(arr)/sizeof(arr[0]);
    int k=3;
    
    printMaxOfEverySbarrayOfSizeK(arr,n,k);
	    
    cout<<endl;
	return 0;
}

Output:

12 12 20 35 

JAVA:

import java.util.*;
public class Main {
    public static void printMaxOfEverySbarrayOfSizeK(int a[],int n,int k){
        
        // Create the upto array.
        int[] upto = new int[n];
  
        // Create the stack.
        Stack <Integer> st = new Stack<>();
        st.push(0);
        
        // Run loop form 1 to n-1 
        for (int i = 1; i < n; i++)
        {
            //Pop out all the indexes from the 
            //stack for which a[st.top] is less than
            //current element and we will update the 
            //value of upto[stack.top] to current index-1.
            while (!st.isEmpty() && a[st.peek()] < a[i])
            {
                upto[st.peek()] = i - 1;
                st.pop();
            }
            //Push i
            st.push(i);
        }
        // While stack is not 
        //empty make upto[s.top] = n-1.
        while (!st.isEmpty())
        {
            upto[st.peek()] = n - 1;
            st.pop();
        }
        int j = 0;
        for (int i = 0; i <= n - k; i++)
        {
  
            // j < i is to check whether the
            // jth element is outside the window
            while (j < i || upto[j] < i + k - 1)
            {
                j++;
            }
            System.out.print(a[j] + " ");
        }
    }
    
	public static void main (String[] args){
	    
	    int arr[]={5, 12, 3, 8, 20, 35};
	    int n=arr.length;
	    int k=3;
	    
	    printMaxOfEverySbarrayOfSizeK(arr,n,k);
	    
        System.out.println();
	}
}

Output:

12 12 20 35 

Python:

def print_max(a, n, k):

    # Create the upto array.
    max_upto=[0 for i in range(n)]

    # Create the stack.
    s=[]
    s.append(0)
    # Run loop from 1 to n-1
    for i in range(1,n):
        # Pop out all the indexes from the
        # stack for which a[st.top] is less than
        # current element and we will update the
        # value of upto[stack.top] to current index-1.
        while (len(s) > 0 and a[s[-1]] < a[i]): 
            max_upto[s[-1]] = i - 1 
            del s[-1] 
        s.append(i) 
    # While stack is not 
    # empty make upto[s.top] = n-1. 
    while (len(s) > 0):
        max_upto[s[-1]] = n - 1
        del s[-1]

    j = 0
    for i in range(n - k + 1):

        # j < i is to check whether the
        # jth element is outside the window
        while (j < i or max_upto[j] < i + k - 1):
            j += 1
        print(a[j], end=" ")
    print()

# Driver code

a = [5, 12, 3, 8, 20, 35]
n = len(a)
k = 3
print_max(a, n, k)

Output:

12 12 20 35 

Complexity Analysis:

• Time Complexity: O(n), Since there are only two traversals of the array.
• Space Complexity: O(n), Since we have used two extra arrays.

Wrapping Up!

In this article, we have learned how to find “Sliding Window Maximum”. We discussed three approaches by which we can solve this problem. This article also contains well-explained codes of both the approaches in the three most popular languages, which are C++, Java, and Python, along with their respective outputs attached to the article for a better understanding of a wide range of our readers.

We sincerely hope that this article has walked you through some deep and important concepts of Arrays, Stack, and Queues and you have learned how we should approach such kinds of problems. We hope that you will now be able to solve this problem as well as its other variations seamlessly and efficiently.

Happy Coding!

People are also reading:

• Depth First Search(DFS)- DSA
• What is Sorting?
• Find the largest & smallest element in the Array
• Circular Linked List
• Linked List
• Types of Data Structure
• Global vs Local Variables
• Algorithms Basics
• DSA – Greedy Algorithms
• DSA – Dynamic Programming