Sliding Window

Sliding Window Maximum (Maximum of All Subarrays of Size K)

Rajeev SinghAlgorithms1 mins read

Sliding Window Maximum (Maximum of All Subarrays of Size K)

Problem statement

Given an array of integers a, and an integer k, find the maximum for each and every contiguous subarray of size k.

Example

Input: a[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3 
Output: 3 3 4 5 5 5 6
Explanation: 
Maximum of subarray {1, 2, 3} is 3
Maximum of subarray {2, 3, 1} is 3
Maximum of subarray {3, 1, 4} is 4
Maximum of subarray {1, 4, 5} is 5
Maximum of subarray {4, 5, 2} is 5
Maximum of subarray {5, 2, 3} is 5
Maximum of subarray {2, 3, 6} is 6

Solution

Brute force

A basic brute force algorithm is to iterate over the array, consider every subarray of size k, and find the maximum in every subarray.

import java.util.Scanner;

public class MaxOfAllSubarraysOfSizeK {
    private static int[] maxofAllSubarray_BruteForce(int[] a, int k) {
        int n = a.length;
        int[] maxOfSubarrays = new int[n - k + 1];
        int idx = 0;

        for(int i = 0; i <= n-k; i++) {
            int maxElement = Integer.MIN_VALUE;
            for(int j = i; j < i+k; j++) {
                if(maxElement < a[j]) {
                    maxElement = a[j];
                }
            }
            maxOfSubarrays[idx++] = maxElement;
        }

        return maxOfSubarrays;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }
        int k = keyboard.nextInt();
        keyboard.close();
        
        int[] result = maxofAllSubarray_BruteForce(a, k);
        for(int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }    
        System.out.println();
    }
}

The time complexity of the brute force algorithm is O(n*k).

Sliding Window

This problem is a variant of the problem First negative number in every window of size k.

If you closely observe the way we calculate the maximum in each k-sized subarray, you will notice that we’re doing repetitive work in the inner loop. Let’s understand it with an example: 

Input: a[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3

For the above example, we first calculate the maximum in the subarray {1, 2, 3}, then we move on to the next subarray {2, 3, 1} and calculate the maximum. Notice that, there is an overlap in both the subarrays:

1 2 3
  2 3 1

So we’re calculating the maximum in the overlapping part (2, 3) twice. We can utilize the sliding window technique to save us from re-calculating the maximum in the overlapping subarray and improve the run-time complexity.

In the sliding window technique, we consider each k-sized subarray as a sliding window. To calculate the maximum in a particular window (2, 3, 1), we utilize the calculation done for the previous window (1, 2, 3).

Since we want to utilize the calculation from the previous window, we need a way to store the calculation for the previous window. We’ll use a PriorityQueue to store the elements of the sliding window in decreasing order (maximum first).

The remaining explanation is same as the previous problem we solved using the same technique: First negative number in every window of size k.

Let’s look at the complete implementation:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class MaxOfAllSubarraysOfSizeK {
    private static int[] maxofAllSubarray(int[] a, int k) {
        int n = a.length;
        int[] maxOfSubarrays = new int[n-k+1];
        int idx = 0;

        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        int windowStart = 0;
        for(int windowEnd = 0; windowEnd < n; windowEnd++) {
            q.add(a[windowEnd]);

            if(windowEnd-windowStart+1 == k) { // We've hit the window size. Find the maximum in the current window and Slide the window ahead
                int maxElement = q.peek();
                maxOfSubarrays[idx++] = maxElement;

                if(maxElement == a[windowStart]) { // Discard a[windowStart] since we are sliding the window now. So it is going out of the window.
                    q.remove();
                }

                windowStart++; // Slide the window ahead
            }
        }
        return maxOfSubarrays;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }
        int k = keyboard.nextInt();
        keyboard.close();
        
        int[] result = maxofAllSubarray(a, k);
        for(int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }    
        System.out.println();
    }
}